Monday, November 10, 2014

[LeetCode] 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.

思路:
1. Tree depth的定义:为当前节点左右subtree depth中的较大值加1.

depth(root) = max[ depth(root->left), depth(root->right) ] + 1

而对NULL节点的depth在有的书上定义为-1,有的书上定义为0。但这个定义并不影响对balance binary tree的判断,所以这里假设NULL节点的depth为0,即leaf节点的depth为1.

2. 如何判断balance?

(1). 一个binary tree中有任何一个subtree不平衡,那么整个tree不平衡。

(2) 当x->left和x->right的subtree都平衡时,只有abs(depth(x->left) - depth(x->right))<=1时,以x的subtree才平衡。

3. 如何递归?

Bottom-up递归,因为只有当某一节点左右子树的depth以及左右子树是否平衡都得知以后,才能判断该节点为根的树是否平衡,以及求得该节点的depth。

Base case: NULL节点depth返回0。

4. 函数返回什么?

函数即要返回当前节点为根的树的depth,以便于父节点判断平衡和计算depth。同时也需要返回该树是否平衡的判断。可以将两个返回值合并在一起:由于最小的depth为0(NULL节点),在返回depth时可以以 -1 来表示该子树不平衡。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool isBalanced(TreeNode *root) {
        return findDepth(root)==-1 ? false : true;
    }
    
    int findDepth(TreeNode *root) {
        if(!root) return 0;
        
        int leftDepth = findDepth(root->left);      // left subtree depth
        if(leftDepth==-1) return -1;
        
        int rightDepth = findDepth(root->right);    // right subtree depth
        if(rightDepth==-1) return -1;
        
        if(abs(leftDepth-rightDepth)>1) return -1;
        
        return max(leftDepth,rightDepth)+1;
    }
};

总结:

代码中ln 11之所以不和ln 14合并放在ln 13之后,是因为当左子树不平衡时,没有必要再对右子树求depth,直接返回-1即可。这类代码中的剪枝优化需要经常注意。

2 comments: