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: 
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