Google+ Followers

Wednesday, January 16, 2013

[LeetCode] Balanced Binary Tree Solution


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 everynode never differ by more than 1.
» Solve this problem

[Thoughts]
recursion. For each node, check the left branch and right branch.

[Code]
1:    bool isBalanced(TreeNode *root) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(root == NULL) return true;  
5:      int val = GetBalance(root);  
6:      if(val ==-1) return false;  
7:      return true;      
8:    }    
9:    int GetBalance(TreeNode* node)  
10:    {  
11:      if(node == NULL)  
12:        return 0;  
13:      int left = GetBalance(node->left);  
14:      if(left == -1) return -1;  
15:      int right = GetBalance(node->right);  
16:      if(right == -1) return -1;  
17:      if(left-right>1 || right-left>1)  
18:        return -1;  
19:      return left>right? left+1:right+1;  
20:    }   



Post a Comment