110. 平衡二叉树

原题链接：

110. 平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/description/

完成情况：

解题思路：

就是要算高度，然后比较每一次迭代过程中的高度。

参考代码：

递归法：

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class _110平衡二叉树_递归法 {
    /**
     *一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root)!= -1;
    }

    /**
     *
     * @param root
     * @return
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

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

迭代法

package 代码随想录.树.二叉树;

import 代码随想录.树.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _110平衡二叉树_迭代 {
    /**
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> myStack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (!myStack.isEmpty() || root!= null) {
            while (root!= null) {
                myStack.push(root);
                root = root.left;
            }
            TreeNode node = myStack.peek();
            // 右结点为null或已经遍历过
            if (node.right == null || node.right == prev) {
                if (Math.abs(getHeight(node.left) - getHeight(node.right)) > 1) {
                    return false;
                }
                myStack.pop();
                prev = node;
                root = null;// 当前结点下，没有要遍历的结点了
            }else {
                root = node.right;
            }
        }
        return true;
    }

    /**
     * 层序遍历，求结点的高度
     *
     * @param node
     * @return
     */
    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        }
        Deque<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(node);
        int height = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            height++;
            while (size > 0) {
                TreeNode curNode = queue.poll();
                if (curNode.left!= null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right!= null) {
                    queue.offer(curNode.right);
                }
            }
        }
        return height;
    }
}

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

错误经验吸取