Leetcode：检查二叉树是否平衡

Question

我正在解决 leetcode 问题，关于检查特定二叉树是否高度平衡。其表述如下：

给定一棵二叉树，确定它是否是高度平衡的。

提供高度平衡树的定义：

高度平衡二叉树是深度为 每个节点的两个子树的差异永远不会超过一个。

递归解决方案很简单：

public boolean isBalanced(TreeNode root){
    return checkBalance(root) != -1;
}

private int checkBalance(TreeNode root){
    if(root == null){
        return 0;
    }
    int leftHeight = checkBalance(root.left);
    int rightHeigth = checkBalance(root.right);
    if(leftHeight == -1 || rightHeigth == -1 || Math.abs(leftHeight - rightHeigth) > 1){
        return -1;
    }
    return Math.max(leftHeight, rightHeigth) + 1;
}

当我尝试迭代实现它时，问题出现了。

使用与递归解决方案相同的 DFS 方法，问题是标准 DFS 实现使用自上而下的迭代，但这里需要自下而上迭代，即开始每个叶子检查它们的根是否平衡.

您能否给出如何实施的提示？

Answer 1

您必须维护一个显式堆栈。将节点对及其左子树的高度放在该堆栈上（如果已知，否则为 -1）。当从堆栈中弹出条目时还可以计算右子树的高度时，就可以验证平衡。

public class Info {
    public TreeNode node;
    public int leftHeight = -1;

    public Info(TreeNode node) {
        this.node = node;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;

        Stack<Info> path = new Stack<>();
        Info curr = new Info(root);
        while (true) {
            if (curr.leftHeight == -1) {
                while (curr.node.left != null) {
                    path.push(curr);
                    curr = new Info(curr.node.left);
                }
                curr.leftHeight = 0; // No left child
            }
            if (curr.node.right != null) {
                path.push(curr);
                curr = new Info(curr.node.right);
            } else { 
                int rightHeight = 0; // No right child
                while (curr.leftHeight > -1) {
                    if (Math.abs(curr.leftHeight - rightHeight) > 1) {
                        return false;
                    }
                    if (curr.node == root) {
                        return true;
                    }
                    rightHeight = Math.max(curr.leftHeight, rightHeight) + 1;
                    curr = path.pop();
                }
                curr.leftHeight = rightHeight;
            }
        } 
    }
}