【Java数据结构】---二叉树OJ

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.判断结构是否一样
        if(p!=null&&q==null || p==null&&q!=null){
            return false;
        }
        //要么都为null 要么都不为null
        if(p==null&&q==null){
            return true;
        }
        //2.判断值是否一样
        if(p.val!=q.val){
            return false;
        }
        //值一样(左子树与左子树比较)
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //当前子树是否和根结点一样
        if(root==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true; 
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1.判断结构是否一样
        if(p!=null&&q==null || p==null&&q!=null){
            return false;
        }
        //要么都为null 要么都不为null
        if(p==null&&q==null){
            return true;
        }
        //2.判断值是否一样
        if(p.val!=q.val){
            return false;
        }
        //值一样(左子树与左子树比较)
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        invertTree(root.left);
        invertTree(root.right); 
        return root;
        
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
        
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        //左树不为空并且右树为空  或者  左树为空右树不为空
        if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
            return false;
        }
        //左树为空并且右树为空
        if(leftTree==null&&rightTree==null){
            return true;
        }
        //左树的值不等于右树的值
        if(leftTree.val!=rightTree.val){
            return false;
        }
        //返回左树的左结点 右树的右结点 并且 左树的右结点 右树的左结点
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
        }
        
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        //如果一棵树是平衡二叉树 那么他的每颗子树都是平衡二叉树（左右子树高度差<=1）
        if(root==null) return true;
        return getHright(root)>=0;
    }
    public int getHright(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight=getHright(root.left);
        if(leftHeight<0){
            return -1;
        }
        int rightHeight=getHright(root.right);

        //绝对值
        if(rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else{
            return -1;
        }
    }
}