LeetCode-110 Balanced Binary Tree

发表于 | 分类于 | 
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//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 left and right subtrees of every node differ in height by no more than 1. 
// 
//
// 
//
// Example 1: 
//
// Given the following tree [3,9,20,null,null,15,7]: 
//
// 
//    3
//   / \
//  9  20
//    /  \
//   15   7 
//
// Return true. 
// 
//Example 2: 
//
// Given the following tree [1,2,2,3,3,null,null,4,4]: 
//
//  [1,2,2,3,null,null,3,4,null,null,4]
//       1
//      / \
//     2   2
//    / \
//   3   3
//  / \
// 4   4
//
//
// Return false.
// Related Topics Tree Depth-first Search


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    // 递归实现
    // 取左右子树的最大值比较
    // 递归出口返回0
    // 递归中间层+1返回
    // 从上到下依次，遇到不平衡即可返回

    public int branchHeight(TreeNode node) {
        // 递归出口
        if (null == node) {
            return 0;
        }

        int leftH = branchHeight(node.left);
        int rightH = branchHeight(node.right);

        int ret = (leftH > rightH ? (leftH + 1) : (rightH + 1));

        return ret;
    }


    /**
     * 存在的问题： 多次重复递归
     * 优化：能不能一次递归，把值深度记录下来？
     */
    public boolean isBalanced(TreeNode root) {

        if (null == root) {
            return true;
        }


        int leftH = branchHeight(root.left);
        int rightH = branchHeight(root.right);

        boolean isBalance = (-1 <= (leftH - rightH) && (leftH - rightH) <= 1);

        if (isBalance) {
            return isBalanced(root.left) && isBalanced(root.right);
        }

        return isBalance;
    }


}
//leetcode submit region end(Prohibit modification and deletion)