binary-tree - 二分木が反復関数でバランスが取れているかどうかを確認しますか?

Question

二分木がバランスが取れているかどうかを判断するために、非再帰関数を実装する必要があります。

誰？

ありがとう！！！

Answer 1

「バランス」とは、AVL ツリーの意味での「高さのバランス」を意味し、各ノードの任意の情報を格納できると仮定すると、

• ポストオーダーのノードごとに、
  • いずれかの子が存在しない場合は、それぞれの高さが 0 であると想定します。
  • 両方の子の高さが 2 倍以上異なる場合、ツリーはバランスが取れていません。
  • それ以外の場合、このノードの高さは両方の子の高さのうち大きい方になります。
• このポイントに到達すると、ツリーはバランスが取れています。

ポストオーダー トラバーサルを実行する 1 つの方法:

• ルートから開始
• ループ
  • このノードの左の子が存在し、その高さが計算されていない場合は、次に左の子にアクセスします。
  • それ以外の場合、このノードの右の子が存在し、その高さが計算されていない場合は、次に右の子にアクセスします。
  • そうしないと
    • このノードの高さを計算し、早期に返す可能性があります
    • このノードがルートでない場合は、次にその親にアクセスします。
• このポイントに到達すると、ツリーはバランスが取れています。

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);
    }
}