二叉樹経典練習問題（基礎）--JAVA

は、一本の木が完全二叉の木かどうかを判定する

。

は、2本の木が同じかどうかを判定する

。

は、2本の木が同じ構造とノード値のサブツリー

があるかどうかを判定する。

木の最大深度を見つける

は、一本の木が高いバランスの二叉樹であるかどうかを判定する（一つの二叉樹は、各ノードの左右の二つのサブツリーの高さ差の絶対値が1を超えない）

。

は、一本の木が対称かどうかを判定する

。

は、ツリーが対称性をミラーリングしているかどうかを判定する

。

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x ;
    }

    static TreeNode build() {
        //  build       ，       
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.left = G;
        C.right = F;
        return A;
    }

    boolean isCompleteTree(TreeNode root) {
        //             ：
        //1.            ：
        //                
        //       ，        
        //         ，     
        if(root == null) {
            return true;
        }
        boolean isFirstStep = true;
        //      
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer((TreeNode) root);

        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
        }
        return isFirstStep;
    }

    public boolean isSameTree(TreeNode s, TreeNode t) {
        //         
        if(s == null && t == null) {
            return true;
        }
        if(s == null ||t == null){
            return false;
        }
        return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
    public boolean isSubtree(TreeNode s, TreeNode t) {
        //          s   t，   s        t              。
        // s         s                。
        // s              
        if(s == null) {
            return false;
        }
        //     s :  s    t
        return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    public int maxDepth(TreeNode root) {
        //       ，       
        //                           
        //ps:               

        //     = 1 + max（     ，      ）
        if(root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
    }

    public boolean isBalanced(TreeNode root) {
        //       ，              .
        //            ：
        //                           1.
        if(root == null) {
            return true;
        }
        if(root.left == null && root.right == null) {
            return true;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return (left - right <= 1 && left - right >= -1) && isBalanced(root.left) && isBalanced(root.right);
    }

    private boolean isMirrow(TreeNode t1, TreeNode t2) {
        //         ：
        //        ，        (      )
        //           
        //&&    .left     .right     
        //&&    .right     .left     
        if(t1 == null && t2 == null) {
            return true;
        }
        if(t1 == null || t2 == null) {
            return false;
        }
        return (t1.val == t2.val) && isMirrow(t1.left, t2.right) && isMirrow(t1.right, t2.left);
    }
    public boolean isSymmetric(TreeNode root) {
        //       ，           
        if(root == null) {
            return true;
        }
        return isMirrow(root.left, root.right);
    }
}