首页 > 代码库 > [LeetCode] [Balanced Binary Tree 2012-10-08 ]

[LeetCode] [Balanced Binary Tree 2012-10-08 ]

2024-07-04 17:31:40   225人阅读

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.

The key problem is that recursive func should return not only T/F to indicate if subtree is balanced, but also the depth for parent root to decide if left/right has the same depth.

we use the TreeNode->val to store the depth, so an initialize of val is needed at first.

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
 
    void ResetTree(TreeNode * root)
    {
        if(root == NULL)
        {
            return;
        }
        root->val = 0;
        ResetTree(root->left);
        ResetTree(root->right);
    }
     
    bool treeSet = false;
     
    bool isBalanced(TreeNode *root) {
         
        if(treeSet == false)
        {
            ResetTree(root);
            treeSet = true;
        }
        if(root == NULL)    return true;
         
        bool b1 = isBalanced(root->left);
        bool b2 = isBalanced(root->right);
        if(b1 == false || b2 == false)
        {
            return false;
        }
         
        int d1 = 0;
        int d2 = 0;
        if(root->left)
        {
            d1 = root->left->val;
        }
        if(root->right)
        {
            d2 = root->right->val;
        }
        if(d1 > d2)
        {
            root->val = d1+1;
        }
        else
        {
            root->val = d2+1;
        }
        if((d1-d2)>1 || (d1-d2)<-1)
        {
            return false;
        }
        return true;
    }
};

 

 

 


联系
我们