[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即可。这类代码中的剪枝优化需要经常注意。