LeetCode Balanced Binary Tree: DFS and O(N) Time
Overview
LeetCode Balanced Binary Tree Solution: DFS to get the height of every subtree rooted at each node and test it against the balance definition, all in O(N) pass.
LeetCode Balanced Binary Tree
Given a binary tree, determine if it is heightbalanced.
For this problem, a heightbalanced 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.
Analysis: DFS and O(N) Time
This is just a simple application of DFS, just do a depth first search and each subtree whether it is balanced by the definition, if all subtree satisfy, then the whole tree is balanced, the time complexity is O(  V  +  E  ), linear to the number of nodes plus the number of edges. The additional effects is that we can get all the height in a single pass with O(N) time. The following code is accepted by the LeetCode OJ to pass this Balanced Binary Tree problem: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int dfs(TreeNode *root, bool *pFlag) {
if (NULL == root  false == *pFlag )
return 0;
int l = dfs(root>left, pFlag);
int r = dfs(root>right, pFlag);
*pFlag = *pFlag && (abs(l  r) <= 1);
return max(l, r) + 1;
}
bool isBalanced(TreeNode *root) {
bool ret = true;
dfs(root, &ret);
return ret;
}
};
Remarks

To get all the heights of every node in a tree, we also only need one DFS with the time complexity as O( V + E )  Tree needs to use struct to define node, and there is a post about C/C++ struct “ The Usage of C/C++ struct”
Summary
LeetCode Balanced Binary Tree Solution: DFS to get the height of every subtree rooted at each node and test it against the balance definition, all in O(N) pass.
Written on January 13, 2013