binary-tree - 检查二叉树是否与迭代函数平衡？

Question

我需要实现一个非递归函数来确定二叉树是否平衡。

任何人？

谢谢！！！

Answer 1

假设“平衡”是指 AVL 树意义上的“高度平衡”，并且您可以为每个节点存储任意信息，

• 对于后序中的每个节点，
  • 如果任何一个孩子都不存在，则假设其各自的高度为 0。
  • 如果两个孩子的身高相差超过一，则树不平衡。
  • 否则，此节点的高度是两个孩子的高度中较大的一个。
• 如果达到这一点，则树是平衡的。

执行后序遍历的一种方法：

• 从根开始
• 环形
  • 如果这个节点的左孩子存在并且没有计算它的高度，那么接下来访问它的左孩子。
  • 否则，如果该节点的右孩子存在并且没有计算其高度，则接下来访问其右孩子。
  • 别的
    • 计算此节点的高度，可能提前返回
    • 如果这个节点不是根节点，接下来访问它的父节点。
• 如果达到这一点，则树是平衡的。

Answer 2

尝试这个，

public class BalancedBinaryTree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if (root==null) {
             return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        Map<TreeNode, Integer> map = new HashMap<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left==null || (node.left!=null && map.containsKey(node.left))) && (node.right==null || (node.right!=null && map.containsKey(node.right)))) {
                int right = (node.right==null) ? 0 : map.get(node.right);
                int left = (node.left==null) ? 0 : map.get(node.left);
                if (Math.abs(right-left)>1) {
                    return false;
                } else {
                    map.put(node, Math.max(right, left)+1);
                }
            } else {
                if (node.left!=null && !map.containsKey(node.left)) {
                    stack.push(node);
                    stack.push(node.left);
                } else {
                    stack.push(node);
                    stack.push(node.right);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BalancedBinaryTree b = new BalancedBinaryTree();
        boolean v = b.isBalanced(new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7))));
        System.out.println(v);
        v = b.isBalanced(new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4), new TreeNode(4)), new TreeNode(3)), new TreeNode(2)));
        System.out.println(v);
        v = b.isBalanced(new TreeNode(1, new TreeNode(2, new TreeNode(4, new TreeNode(8), null), new TreeNode(5)), new TreeNode(3, new TreeNode(6), null)));
        System.out.println(v);
    }
}