代码随想录day14| 226.翻转二叉树 、101. 对称二叉树 、 104.二叉树的最大深度、 111.二叉树的最小深度

226.翻转二叉树

思路

使用递归将子树的左右子树翻转

class Solution {
    public TreeNode invertTree(TreeNode root) {
        return reverseTree(root);

    }

    public TreeNode reverseTree(TreeNode root) {
        if(root== null){
            return null;
        }
        swapNode(root);
        reverseTree(root.left);
        reverseTree(root.right);
        return root;
    }
    public void swapNode(TreeNode root) {
        TreeNode node = new TreeNode();
        node = root.left;
        root.left = root.right;
        root.right = node;
    }
}

01. 对称二叉树

思路

使用递归判断左右子树是否对称，这里使用后序遍历且返回boolean值，只有左子树是否对称的结果，右子树的结果都为true,则当前根节点为true

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
        if(left == null && right != null){
            return false;
        }else if(left != null && right == null){
            return false;
        }else if(left == null && right == null){
            return true;
        }else if(left.val != right.val){
            return false;
        }
        //这里注意别比较相等时候，弄清楚结束边界
        // else if(left.val == right.val){
        //     return true;
        // }

        boolean a =  compare(left.right, right.left);
        boolean b =  compare(left.left, right.right);
        return a && b;

    }
}

104.二叉树的最大深度

思路

• 二叉树的最大深度就是根节点的最大高度
• 递归函数传入两个参数root和deepth，deepth用来更新当前高度。
• 每次递归返回当前节点的最大高度，取左子树和右子树的高度最大值加一（1+Math.max(left,right)）

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

    }
}

111.二叉树的最小深度

class Solution {
    /**
     * 递归法，相比求MaxDepth要复杂点
     * 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if (root.left == null) {
            return rightDepth + 1;
        }
        if (root.right == null) {
            return leftDepth + 1;
        }
        // 左右结点都不为null
        return Math.min(leftDepth, rightDepth) + 1;
    }
}