Balanced Binary Tree · 數據結構與算法/leetcode/lintcode題解

# Balanced Binary Tree ### Source - lintcode: [(93) Balanced Binary Tree](http://www.lintcode.com/en/problem/balanced-binary-tree/) ~~~ Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7} A) 3 B) 3 / \ \ 9 20 20 / \ / \ 15 7 15 7 The binary tree A is a height-balanced binary tree, but B is not. ~~~ ### 題解 - 遞歸根據題意，平衡樹的定義是兩子樹的深度差最大不超過1，顯然使用遞歸進行分析較為方便。既然使用遞歸，那么接下來就需要分析遞歸調用的終止條件。和之前的 [Maximum Depth of Binary Tree | Algorithm](http://algorithm.yuanbin.me/zh-cn/binary_tree/maximum_depth_of_binary_tree.html) 類似，`NULL == root`必然是其中一個終止條件，返回`0`；根據題意還需的另一終止條件應為「左右子樹高度差大于1」，但對應此終止條件的返回值是多少？——`INT_MAX` or `INT_MIN`？想想都不合適，為何不在傳入參數中傳入`bool`指針或者`bool`引用咧？并以此變量作為最終返回值，此法看似可行，先來看看鄙人最開始想到的這種方法。 ### C++ Recursion with extra bool variable ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: True if this Binary tree is Balanced, or false. */ bool isBalanced(TreeNode *root) { if (NULL == root) { return true; } bool result = true; maxDepth(root, result); return result; } private: int maxDepth(TreeNode *root, bool &isBalanced) { if (NULL == root) { return 0; } int leftDepth = maxDepth(root->left, isBalanced); int rightDepth = maxDepth(root->right, isBalanced); if (abs(leftDepth - rightDepth) > 1) { isBalanced = false; // speed up the recursion process return INT_MAX; } return max(leftDepth, rightDepth) + 1; } }; ~~~ #### 源碼解析如果在某一次子樹高度差大于1時，返回`INT_MAX`以減少不必要的計算過程，加速整個遞歸調用的過程。初看起來上述代碼好像還不錯的樣子，但是在看了九章的實現后，瞬間覺得自己弱爆了... 首先可以確定`abs(leftDepth - rightDepth) > 1`肯定是需要特殊處理的，如果返回`-1`呢？咋一看似乎在下一步返回`max(leftDepth, rightDepth) + 1`時會出錯，再進一步想想，我們能否不讓`max...`這一句執行呢？如果返回了`-1`，其接盤俠必然是`leftDepth`或者`rightDepth`中的一個，因此我們只需要在判斷子樹高度差大于1的同時也判斷下左右子樹深度是否為`-1`即可都返回`-1`，不得不說這種處理方法要精妙的多，贊！ ### C++ Recursion without extra bool variable ~~~ /** * forked from http://www.jiuzhang.com/solutions/balanced-binary-tree/ * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: True if this Binary tree is Balanced, or false. */ bool isBalanced(TreeNode *root) { return (-1 != maxDepth(root)); } private: int maxDepth(TreeNode *root) { if (NULL == root) { return 0; } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); if (leftDepth == -1 || rightDepth == -1 || \ abs(leftDepth - rightDepth) > 1) { return -1; } return max(leftDepth, rightDepth) + 1; } }; ~~~