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 #include <cstdlib>
 2 #include <iostream>
 3 
 4 struct TreeNode{
 5     int val;
 6     TreeNode* left;
 7     TreeNode* right;
 8     TreeNode(int x):val(x),left(nullptr),right(nullptr){}
 9 };
10 
11 class Solution {
12 public:
13     bool isBalanced(TreeNode* root) {
14         int depth=0;
15         return helper(root,depth);
16     }
17     bool helper (TreeNode* root,int& depth) {
18         if (root == nullptr){
19             depth = 0;
20             return true;
21         }
22         int ld,rd;
23         if(helper(root->left,ld) && helper(root->right,rd)){
24             if(abs(ld-rd)>1){
25                 return false;
26             }
27             depth = ld>rd? ld+1 : rd+1;
28         }
29     }
30 };
31 
32 /**
33 Function:compute the depth of a binary tree.
34 */
35 
36 int treeDepth(TreeNode* root)
37 {
38     if(!root) return 0;
39     int ld = treeDepth(root->left);
40     int rd = treeDepth(root->right);
41     return ld > rd ? ld + 1 : rd + 1;
42 }
43 
44 int main()
45 {
46     TreeNode* root = new TreeNode(1);
47     root->left = new TreeNode(2);
48     root->right = new TreeNode(5);
49     root->left->right = new TreeNode(3);
50     root->left->right->right = new TreeNode(4);
51 
52     Solution s;
53     s.isBalanced(root);
54     std::cout << treeDepth(root) << std::endl;
55 
56     return 0;
57 }