您现在的位置是：首页 >其他 >代码随想录算法训练营第十四天 | LeetCode226反转二叉树、101对称二叉树、104二叉树的最大深度、111二叉树的最小深度网站首页其他

 226.反转二叉树：

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

不论用哪种遍历，哪种顺序，也就是在每一步操作的时候将左右孩子交换即可，甚至进入下一步的时候，递归/入栈/入队列的顺序都无所谓。为了复习几种都写下。

class Solution {
    // 层序/深度优先，递归
    public TreeNode invertTree(TreeNode root) {
        recursion(root);
        return root;
    }

    public void recursion(TreeNode root){
        if(root == null)
            return;
        TreeNode node = root.right;
        root.right = root.left;
        root.left = node;

        recursion(root.left);
        recursion(root.right); 
    }

    // 层序优先，迭代
    public TreeNode invertTree(TreeNode root){
        Deque<TreeNode> stack = new ArrayDeque<>();
        if(root != null)
            stack.offer(root);
        while(!stack.isEmpty()){            
            int size = stack.size();
            while(size-- > 0){
                TreeNode node = stack.peek();
                stack.poll();
                TreeNode temp = node.right;
                node.right = node.left;
                node.left = temp;
                if(node.right != null)
                    stack.offer(node.right);
                if(node.left != null)
                    stack.offer(node.left);
            }
        }
        return root;
    }
    
    // 深度优先，迭代
    public TreeNode invertTree(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if(root != null)
            stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.peek();
            if(node != null){
                stack.pop();
                stack.push(null);
                TreeNode temp = node.right;
                node.right = node.left;
                node.left = temp;
                if(node.right != null)
                    stack.push(node.right);
                if(node.left != null)
                    stack.push(node.left);
            }else{
                stack.pop();
            }
        }
        return root;
    }
}

101.对称二叉树：

我本来想的是联动一下上一题，先层序遍历出一个结果存入List，再将这棵树反转，结果存入List，最后对比两个List的值是否完全一致，是的话则是对称。但这样要遍历两次很麻烦。代码随想录上看到解析，可以用递归和迭代两种方式，重点是同时对比内/外侧。

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;
        if(left == null && right != null)
            return false;
        if(left == null && right == null)
            return true;
        if(left.val != right.val)
            return false;       
        
        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        return outside && inside;
    }

    /**
     * 迭代法
     * 使用双端队列，相当于两个栈
     */
    public boolean isSymmetric2(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();
            if (leftNode == null && rightNode == null) {
                continue;
            }
//            if (leftNode == null && rightNode != null) {
//                return false;
//            }
//            if (leftNode != null && rightNode == null) {
//                return false;
//            }
//            if (leftNode.val != rightNode.val) {
//                return false;
//            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            deque.offerFirst(leftNode.left);
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }
}

104.二叉树的最大深度：

最大深度就是层数，所以用层序优先即可。层序迭代/递归都可以和最基本的差不多。注意用深度的时候，后序的左右中，中间的=左右max+1，其实是高度的思路，从下往上；而前序的中左右才是真正的深度的思路，从上到下。代码可见：代码随想录

class Solution {
    //不想递归return用一个max的话要放在solution里而不是函数里
    int max = 0;
    public int maxDepth(TreeNode root) {
        recursion(root, 0);
        return max;
    }

    public void recursion(TreeNode root, int deep){
        if(root == null)
            return;
        deep++;
        if(max<deep)
            max = deep;
        recursion(root.left, deep);
        recursion(root.right, deep);        
    }

    // 一般递归
    public int maxDepth(TreeNode root) {
        return recursion(root, 0);
    }

    public int recursion(TreeNode root, int deep){
        if(root == null)
            return deep;
        deep++;
        int max_left = recursion(root.left, deep);
        int max_right = recursion(root.right, deep);
        return Math.max(max_left, max_right);
    }
    //还有迭代法，就是基础的层序
}

111.二叉树的最小深度：

看上去和上一道很像，但实际不一样。要注意去min的条件是左右孩子都为null，不是其中一个为null。还是喜欢用层序遍历，递归和迭代都可以。

class Solution {
    //递归
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        return recursion(root, 0);
    }

    public int recursion(TreeNode root, int deep){
        deep++;
        if(root.left == null && root.right == null)
            return deep;
        int min_left = 100001;
        int min_right = 100001;
        if(root.left != null)
            min_left = recursion(root.left, deep);
        if(root.right != null)
            min_right = recursion(root.right, deep);
        return Math.min(min_left, min_right);
    }

    // 迭代
    public int minDepth(TreeNode root){
        int min = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root != null)
            queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            min++;
            while(size-- > 0){
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null)
                    return min;
                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
            }
        }
        return min;
    }
}