二叉树基本算法

问题1

二叉树的高度

原理

• 递归遍历左侧二叉树找到最大值
• 递归遍历右侧二叉树找到最大值
• 返回左侧和右侧结构较大的

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left,right)+1;
    }
}

注意事项

• 左侧的高度+右侧的高度之后需要+1，＋1的含义是当前层。

问题2

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

原理

• 镜像树的原理是：左边右边反转
• 递归执行此过程
• 终止条件是二叉树当前节点为空

代码

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode newHead = new TreeNode(root.val);
        newHead.left = mirrorTree(root.right);
        newHead.right = mirrorTree(root.left);
        return newHead;
    }

    
}

注意事项

• 注意是递归执行，递归的过程无需关系，记住只处理好当前层就好了。

问题3

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

原理

• 对称二叉树的定义：左边的二叉树是右边的二叉树的镜像
• 因此有left.left==right.right&&left.right==right.left
• 空二叉树为对称二叉树

代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return sysmetric(root.left,root.right);
    }

    private boolean sysmetric(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        boolean isLeft = sysmetric(left.left,right.right);
        boolean isRight = sysmetric(left.right,right.left);
        return left.val==right.val&&isLeft&&isRight;
    }


}

注意事项

• 空树为对称二叉树
• left==null&&right==null 为对称二叉树，left==null||right==null为非对称二叉树

问题4

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

原理

• 创建一个新的二叉树，当前节点为t1.val和t2.val之和
• 新二叉树的左子树为，t1的左子树和t2的左子树，新二叉树的右子树为，t1的右子树和t2的右子树
• 递归整个过程

代码

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        TreeNode newRoot = new TreeNode(t1.val+t2.val);
        newRoot.left = mergeTrees(t1.left,t2.left);
        newRoot.right = mergeTrees(t1.right,t2.right);
        return newRoot;
    }
}

注意事项

• 暂无