二叉樹的深度

對于二叉樹的深度的求解，利用遞歸的方式求解很簡單：

下面就來設計這個遞歸算法：

要求一個節點的高度，先求左子樹的高度，然后再求解右子樹的高度。 最后樹的高度就是1+max(left_depth, right_depth)。 int leftLen = depth_tree(root->left); int rightLen = depth_tree(root->right); return 1 + max(leftLen, rightLen); 那么這個遞歸的出口是什么： (1)可以遞歸到1，如果一個節點不為NULL，但是這個節點的左子樹為NULL， 并且右子樹也為NULL，那么返回高度為1。 但是有這種情況：這個節點的左子樹不為NULL，右子樹為NULL，上面求leftLen和rightLen的遞歸還是會傳入NULL。 所以這種遞歸的出口不可行。 (2)索性讓遞歸的出口變成傳入NULL參數，也就是說為NULL單獨遞歸一次函數。 if(root == NULL)return 0; 就這一個出口就能解決所有的。

算法代碼實現：

int depth_tree(TreeNode *root) {if(NULL == root){return 0;}int nLeft = depth_tree(root->left);int nRight = depth_tree(root->right);return 1 + (nLeft > nRight ? nLeft : nRight); }

二叉樹的最低高度

先看二叉樹的最低高度的定義：從根節點都任一個葉子節點中路徑最短的那個就是二叉樹的最低高度。

那么這樣一看，似乎可以這個設計，把最后一句話改為：?return 1 + min(left, right);?但是這樣是不可行的。舉一個簡單的例子：

上面的代碼返回的結果是1，但是這棵樹的最低高度是3，因為要從根到一個葉子節點的長度。所以要修改最后的返回結果，在left和right中，如果有一個為0，則返回另一個的值；當兩個都不是0的時候，才返回二者中較小的那個。

所以代碼實現：

int minDepth(TreeNode* root) {if(!root){return 0;}int left = minDepth(root->left);int right = minDepth(root->right);if(!left){return 1 + right;}else if(!right){return 1 + left;}else {return 1 + min(left, right);} }　　

二叉樹平衡的判定

還是用遞歸的想法，想判定根節點是不是平衡的，如果不是就直接返回false，如果是然后就分別去判斷這個根的左子樹和右子樹是否都是平衡的二叉樹。

代碼實現：

bool IsBalance(TreeNode *root) {if(NULL == root)return true;int left = depth_tree(root->left);int right = depth_tree(root->right);if(abs(left-right) > 1){return false;}return IsBalance(root->left) && IsBalance(root->right); }

但是現在算法的效率還是不夠高，求解root的平衡性的時候，我們遍歷了左子樹和右子樹求解子樹的高度。當我們求解root孩子的平衡性的時候，還要求解root孩子左右子樹的高度，有很大一部分節點重復的被遍歷了。所以效率大大的降低了。

判定二叉樹平衡的高效算法

前面的算法是，對于每一個節點都要去求解它的左右子樹的高度，那么可以利用二叉樹的后序遍歷方式，當遍歷到某個節點的時候，它的左子樹和右子樹都已經遍歷完成，同時要分別帶回左、右子樹的高度，以便左右子樹高度對比。

bool isBalance(TreeNode *root, int *depth) {if(root == NULL){*depth = 0;return true;}int left, right;if(isBalance(root->left, &left) && isBalance(root->right, &right)){int diff = left - right;if(diff >= -1 && diff <=1){*depth = 1 + max(left, right);return true;}}return false; }

這里只是一個后序遍歷帶回高度的算法，每個節點僅僅的遍歷了一次。

轉載于:https://www.cnblogs.com/stemon/p/4868671.html

總結

以上是生活随笔為你收集整理的二叉树深度和平衡二叉树的判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。