本节内容

层序遍历 10道题
226.翻转二叉树
101.对称二叉树 2

层序遍历※

建议：看完本篇可以一口气刷十道题，试一试，层序遍历并不难，大家可以很快刷了十道题。

题目链接：
文章讲解： https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

代码随想录

102.二叉树的层序遍历

官方题目链接： https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目分析

方案一：迭代，使用双端队列的思想

方案一：迭代遍历

使用双端队列的思想，根据其先进先出的特性，将二叉树一层一层进行遍历，其实队列里面的数据，可以引导出下一层的数据，由此来迭代循环

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> deque = new LinkedList<>(); // 此处使用的是队列的思想

        deque.addFirst(root);

        while (!deque.isEmpty()) {
            deque.addLast(null);
            List<Integer> temp = new ArrayList<>();
            while (deque.peek()!= null) {  // peek == peekFirst
                TreeNode poll = deque.poll();  // poll == pollFirst
                temp.add(poll.val);
                
                if (poll.left != null)
                    deque.addLast(poll.left);

                if (poll.right != null)
                    deque.addLast(poll.right);
            }
            deque.poll();
            result.add(temp);
        }

        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了84.23% 的Java用户
内存消耗:42.8 MB,击败了28.10% 的Java用户

方案二：递归遍历

看了题解之后，才写出来的，递归依然有待进一步学习

class Solution {

    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return result;
        }

        recur(root, 0);

        return result;
    }

    private void recur(TreeNode node, Integer depth) {
        if (node == null) return;
        depth++;

        if (depth > result.size()) {
            List<Integer> temp = new ArrayList<>();
            result.add(temp);
        }

        result.get(depth - 1).add(node.val);

        recur(node.left, depth);
        recur(node.right, depth);
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:42.9 MB,击败了26.72% 的Java用户

代码随想录

文章讲解： https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_102-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86
视频讲解： https://www.bilibili.com/video/BV1GY4y1u7b2/

其和我上面写的方案的区别是：对每层数据如何知道其在队列中何时停止，何时正常执行
上述方案中插入一个空节点，当其到了空节点，则意味着此层执行完成；
本方案中维护了一个size此变量，用于保存每层节点的数目。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

这样就实现了层序从左到右遍历二叉树。

代码实现

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //DFS--递归方式
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);
                if (tmpNode.right != null) que.offer(tmpNode.right);
                len--;
            }

            resList.add(itemList);
        }

    }
}

107.二叉树的层次遍历II

官方题目链接： https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

题目分析

方案一

其只是上题 102.二叉树的层序遍历的改版，本题的解题思路是先按照 102.二叉树的层序遍历的求解方法去求解，会得到相关的答案，此时将答案反转一下就是本题的答案了，就是那么简单粗暴。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Deque<TreeNode> deque = new LinkedList<>();

        deque.add(root);

        while (!deque.isEmpty()) {
            deque.addLast(null);
            List<Integer> tem = new ArrayList<>();
            while (deque.peek() != null) {
                TreeNode poll = deque.poll();
                tem.add(poll.val);
                if (poll.left != null)
                    deque.addLast(poll.left);
                if (poll.right != null)
                    deque.addLast(poll.right);
            }
            deque.poll();
            result.add(tem);
        }
        Collections.reverse(result);  // 本题与102.二叉树的层序遍历的区别就是添加了此内容，其他没用任何改变
        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了91.66% 的Java用户
内存消耗:40.9 MB,击败了76.77% 的Java用户

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_107-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E6%AC%A1%E9%81%8D%E5%8E%86-ii

思路：

相对于102.二叉树的层序遍历，就是最后把result数组反转一下就可以了。

代码实现

此代码实现和方案一一致

// 107. 二叉树的层序遍历 II
public class N0107 {

    /**
     * 解法：队列，迭代。
     * 层序遍历，再翻转数组即可。
     */
    public List<List<Integer>> solution1(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();

            int levelSize = que.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode peek = que.peekFirst();
                levelList.add(que.pollFirst().val);

                if (peek.left != null) {
                    que.offerLast(peek.left);
                }
                if (peek.right != null) {
                    que.offerLast(peek.right);
                }
            }
            list.add(levelList);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i-- ) {
            result.add(list.get(i));
        }

        return result;
    }
}

此处代码和官方题解（ https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/solution/er-cha-shu-de-ceng-ci-bian-li-ii-by-leetcode-solut/ ）相似，利用链表可以进行 O(1) 头部插入，最终答案不需要进行反转

/**
 * 思路和模板相同, 对收集答案的方式做了优化, 最后不需要反转
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // 利用链表可以进行 O(1) 头部插入, 这样最后答案不需要再反转
        LinkedList<List<Integer>> ans = new LinkedList<>();

        Queue<TreeNode> q = new LinkedList<>();

        if (root != null) q.offer(root);

        while (!q.isEmpty()) {
            int size = q.size();

            List<Integer> temp = new ArrayList<>();

            for (int i = 0; i < size; i ++) {
                TreeNode node = q.poll();

                temp.add(node.val);

                if (node.left != null) q.offer(node.left);

                if (node.right != null) q.offer(node.right);
            }

            // 新遍历到的层插到头部, 这样就满足按照层次反序的要求
            ans.addFirst(temp);
        }

        return ans;
    }
}

199.二叉树的右视图

官方题目链接： 199. 二叉树的右视图

题目分析

方案一

层序遍历，一层层去找，每次添加最右侧的数据

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        if (root == null) return result;

        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            result.add(queue.peek().val);
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.right != null)
                    queue.offer(poll.right);
                if (poll.left != null)
                    queue.offer(poll.left);
            }
            queue.poll();
        }

        return result;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了81.40% 的Java用户
内存消耗:40 MB,击败了85.53% 的Java用户

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_199-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%8F%B3%E8%A7%86%E5%9B%BE

思路：

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

代码实现

// 199.二叉树的右视图
public class N0199 {
    /**
     * 解法：队列，迭代。
     * 每次返回每层的最后一个字段即可。
     *
     * 小优化：每层右孩子先入队。代码略。
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelSize = que.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = que.pollFirst();

                if (poll.left != null) {
                    que.addLast(poll.left);
                }
                if (poll.right != null) {
                    que.addLast(poll.right);
                }

                if (i == levelSize - 1) {
                    list.add(poll.val);
                }
            }
        }

        return list;
    }
}

637.二叉树的层平均值

官方题目链接： 637. 二叉树的层平均值

题目分析

方案一：广度优先搜索：层序遍历

层序遍历的思想

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        int size = 0; // 每一层数值的个数
        long sum = 0; // 每一层数值的总和
        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            size = 0;
            sum = 0;
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                size++;
                sum += poll.val;
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            queue.poll();
            result.add(1.0 * sum / size);
        }

        return result;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了25.68% 的Java用户
内存消耗:43.2 MB,击败了66.71% 的Java用户

方案二：深度优先搜索

查看官方题解学到的方法： https://leetcode.cn/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();

        List<long[]> sum = new ArrayList<>(); // 数组中，0：总值 1：size

        resuc(root, 0, sum);

        for (long[] ins :
                sum) {
            result.add(1.0 * ins[0] / ins[1]);
        }

        return result;
    }

    private void resuc(TreeNode root, int depth, List<long[]> sum) {
        if (root == null) return;
        depth++;
        if (sum.size() < depth) {
            sum.add(new long[]{0, 0});
        }
        long[] ints = sum.get(depth - 1);
        ints[0] = ints[0] + root.val;
        ints[1] += 1;
        sum.set(depth - 1, ints);

        resuc(root.left, depth, sum);
        resuc(root.right, depth, sum);

    }
}

结果

解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:43.4 MB,击败了49.88% 的Java用户

官方题解

https://leetcode.cn/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Integer> counts = new ArrayList<Integer>();
        List<Double> sums = new ArrayList<Double>();
        dfs(root, 0, counts, sums);
        List<Double> averages = new ArrayList<Double>();
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            averages.add(sums.get(i) / counts.get(i));
        }
        return averages;
    }

    public void dfs(TreeNode root, int level, List<Integer> counts, List<Double> sums) {
        if (root == null) {
            return;
        }
        if (level < sums.size()) {
            sums.set(level, sums.get(level) + root.val);
            counts.set(level, counts.get(level) + 1);
        } else {
            sums.add(1.0 * root.val);
            counts.add(1);
        }
        dfs(root.left, level + 1, counts, sums);
        dfs(root.right, level + 1, counts, sums);
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree/solution/er-cha-shu-de-ceng-ping-jun-zhi-by-leetcode-soluti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_637-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%B9%B3%E5%9D%87%E5%80%BC

思路:

本题就是层序遍历的时候把一层求个总和在取一个均值。

代码实现

// 637. 二叉树的层平均值
public class N0637 {

    /**
     * 解法：队列，迭代。
     * 每次返回每层的最后一个字段即可。
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Deque<TreeNode> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {

            int levelSize = que.size();
            double levelSum = 0.0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode poll = que.pollFirst();

                levelSum += poll.val;

                if (poll.left != null) {
                    que.addLast(poll.left);
                }
                if (poll.right != null) {
                    que.addLast(poll.right);
                }
            }
            list.add(levelSum / levelSize);
        }
        return list;
    }
}

429.N叉树的层序遍历

官方题目链接： 429. N 叉树的层序遍历

题目分析

方案一

此题重点查看一下其定义的相关方法，即可知道如何进行层序遍历了

官方对于节点的定义

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

个人编写的程序

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Deque<Node> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            List<Integer> tem = new ArrayList<>();
            while (queue.peek() != null) {
                Node poll = queue.poll();
                tem.add(poll.val);
                List<Node> chilList= poll.children;
				for (Node node : chilList) {
					queue.offer(node);
                }
            }
            queue.poll();
            result.add(tem);
        }
        return result;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了85.76% 的Java用户
内存消耗:42.9 MB,击败了66.16% 的Java用户

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_429-n%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86

思路:

这道题依旧是模板题，只不过一个节点有多个孩子了

代码实现

// 429. N 叉树的层序遍历
public class N0429 {
    /**
     * 解法1：队列，迭代。
     */
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Node> que = new LinkedList<>();

        if (root == null) {
            return list;
        }

        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelSize = que.size();
            List<Integer> levelList = new ArrayList<>();

            for (int i = 0; i < levelSize; i++) {
                Node poll = que.pollFirst();

                levelList.add(poll.val);

                List<Node> children = poll.children;
                if (children == null || children.size() == 0) {
                    continue;
                }
                for (Node child : children) {
                    if (child != null) {
                        que.offerLast(child);
                    }
                }
            }
            list.add(levelList);
        }

        return list;
    }
}

515.在每个树行中找最大值

官方题目链接： 515. 在每个树行中找最大值

题目分析

方案一

典型的层序遍历

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);
            int maxTemp = queue.peek().val;
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (maxTemp < poll.val) {
                    maxTemp = poll.val;
                }

                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            result.add(maxTemp);
            queue.poll();
        }
        return result;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了87.13% 的Java用户
内存消耗:42.8 MB,击败了59.30% 的Java用户

方案二：深度优先搜索

查看官方题解学到的方法

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        resuc(root, 0, result);

        return result;
    }

    private void resuc(TreeNode root, int leave, List<Integer> result) {
        if (root == null) return;
        leave++;
        if (result.size() < leave) {
            result.add(Integer.MIN_VALUE);
        }

        if (root.val > result.get(leave - 1)) {
            result.set(leave - 1, root.val);
        }

        resuc(root.left, leave, result);
        resuc(root.right, leave, result);
    }
}

结果

解答成功:
执行耗时:1 ms,击败了97.32% 的Java用户
内存消耗:43 MB,击败了40.25% 的Java用户

官方题解

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/solution/zai-mei-ge-shu-xing-zhong-zhao-zui-da-zh-6xbs/

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if (root == null) {
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<Integer>();
        dfs(res, root, 0);
        return res;
    }

    public void dfs(List<Integer> res, TreeNode root, int curHeight) {
        if (curHeight == res.size()) {
            res.add(root.val);
        } else {
            res.set(curHeight, Math.max(res.get(curHeight), root.val));
        }
        if (root.left != null) {
            dfs(res, root.left, curHeight + 1);
        }
        if (root.right != null) {
            dfs(res, root.right, curHeight + 1);
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/solution/zai-mei-ge-shu-xing-zhong-zhao-zui-da-zh-6xbs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_515-%E5%9C%A8%E6%AF%8F%E4%B8%AA%E6%A0%91%E8%A1%8C%E4%B8%AD%E6%89%BE%E6%9C%80%E5%A4%A7%E5%80%BC

思路：

层序遍历，取每一层的最大值

代码实现

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        if(root == null){
            return Collections.emptyList();
        }
        List<Integer> result = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            int max = Integer.MIN_VALUE;
            for(int i = queue.size(); i > 0; i--){
               TreeNode node = queue.poll();
               max = Math.max(max, node.val);
               if(node.left != null) queue.offer(node.left);
               if(node.right != null) queue.offer(node.right);
            }
            result.add(max);
        }
        return result;
    }
}

116.填充每个节点的下一个右侧节点指针

官方题目链接： 116. 填充每个节点的下一个右侧节点指针

题目分析

方案一：层序遍历

先尝试使用层序遍历来解决此问题

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;

        Deque<Node> queue = new LinkedList<>();
        Node nextNode = null;

        queue.offer(root);

        while (!queue.isEmpty()) {
            nextNode = null;
            queue.offer(null);
            while (queue.peek() != null) {
                Node poll = queue.poll();
                poll.next = nextNode;
                nextNode = poll;

                if (poll.right != null)
                    queue.offer(poll.right);
                if (poll.left != null)
                    queue.offer(poll.left);
            }
            queue.poll();
        }
        return root;
    }
}

结果

解答成功:
执行耗时:3 ms,击败了31.52% 的Java用户
内存消耗:42 MB,击败了51.08% 的Java用户

方案二：使用已建立的 nextnext 指针

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;

        Node node = root;
        node.next = null;

        while (node.left != null) {
            Node temp = node;
            while (node.next != null) {
                node.left.next = node.right; // 第一种情况
                node.right.next = node.next.left; // 第二种情况
                node = node.next;
            }
            node.left.next = node.right;
            node.right.next = null;
            node = temp.left;
        }

        return root;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:42.2 MB,击败了30.07% 的Java用户

官方题解

链接： https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/

思路

一棵树中，存在两种类型的 next 指针。

第一种情况是连接同一个父节点的两个子节点。它们可以通过同一个节点直接访问到，因此执行下面操作即可完成连接。

1	`node.left.next = node.right`

第二种情况在不同父亲的子节点之间建立连接，这种情况不能直接连接。

如果每个节点有指向父节点的指针，可以通过该指针找到 nextnext 节点。如果不存在该指针，则按照下面思路建立连接：

完成当前层的连接后，进入下一层重复操作，直到所有的节点全部连接。进入下一层后需要更新最左节点，然后从新的最左节点开始遍历该层所有节点。因为是完美二叉树，因此最左节点一定是当前层最左节点的左孩子。如果当前最左节点的左孩子不存在，说明已经到达该树的最后一层，完成了所有节点的连接。

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        
        // 从根节点开始
        Node leftmost = root;
        
        while (leftmost.left != null) {
            
            // 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针
            Node head = leftmost;
            
            while (head != null) {
                
                // CONNECTION 1
                head.left.next = head.right;
                
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // 指针向后移动
                head = head.next;
            }
            
            // 去下一层的最左的节点
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-2-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_116-%E5%A1%AB%E5%85%85%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%8F%B3%E4%BE%A7%E8%8A%82%E7%82%B9%E6%8C%87%E9%92%88

思路:

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

代码实现

class Solution {
    public Node connect(Node root) {
	Queue<Node> tmpQueue = new LinkedList<Node>();
	if (root != null) tmpQueue.add(root);

	while (tmpQueue.size() != 0){
	    int size = tmpQueue.size();

            Node cur = tmpQueue.poll();
            if (cur.left != null) tmpQueue.add(cur.left);
            if (cur.right != null) tmpQueue.add(cur.right);

	    for (int index = 1; index < size; index++){
		Node next = tmpQueue.poll();
		if (next.left != null) tmpQueue.add(next.left);
		if (next.right != null) tmpQueue.add(next.right);

                cur.next = next;
                cur = next;
	    }
	}

        return root;
    }
}

117.填充每个节点的下一个右侧节点指针II

官方题目链接： 117. 填充每个节点的下一个右侧节点指针 II

题目分析

方案一

层序遍历，
编写的代码和上一题： 116.填充每个节点的下一个右侧节点指针一模一样，没用任何变化直接执行成功

class Solution {
    public Node connect(Node root) {
        if (root == null) return root;

        Deque<Node> queue = new LinkedList<>();
        Node nextNode = null;

        queue.offer(root);

        while (!queue.isEmpty()) {
            nextNode = null;
            queue.offer(null);
            while (queue.peek() != null) {
                Node poll = queue.poll();
                poll.next = nextNode;
                nextNode = poll;

                if (poll.right != null)
                    queue.offer(poll.right);
                if (poll.left != null)
                    queue.offer(poll.left);
            }
            queue.poll();
        }
        return root;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了24.00% 的Java用户
内存消耗:41.9 MB,击败了53.62% 的Java用户

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_117-%E5%A1%AB%E5%85%85%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%8F%B3%E4%BE%A7%E8%8A%82%E7%82%B9%E6%8C%87%E9%92%88ii

思路：

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

代码实现

// 二叉树之层次遍历
class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node node = null;
            Node nodePre = null;

            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    nodePre = queue.poll(); // 取出本层头一个节点
                    node = nodePre;
                } else {
                    node = queue.poll();
                    nodePre.next = node; // 本层前一个节点 next 指向当前节点
                    nodePre = nodePre.next;
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            nodePre.next = null; // 本层最后一个节点 next 指向 null
        }
        return root;
    }
}

104.二叉树的最大深度

官方题目链接： 104. 二叉树的最大深度

题目分析

方案一：层序遍历

层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int maxLeave = 0;

        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.add(null);
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
            }
            queue.poll();
            maxLeave++;
        }
        return maxLeave;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了20.62% 的Java用户
内存消耗:41.6 MB,击败了5.05% 的Java用户

方案二：迭代遍历

class Solution {

    private int maxLeave = 0;
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        recus(root, 0);
        return maxLeave;
    }

    private void recus(TreeNode root, int depth) {
        if (root == null) return;
        depth++;

        if (maxLeave < depth) {
            maxLeave = depth;
        }
        recus(root.left, depth);
        recus(root.right, depth);
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.5 MB,击败了65.83% 的Java用户

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_104-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6

思路：

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

代码实现

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)   return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while (!que.isEmpty())
        {
            int len = que.size();
            while (len > 0)
            {
                TreeNode node = que.poll();
                if (node.left != null)  que.offer(node.left);
                if (node.right != null) que.offer(node.right);
                len--;
            }
            depth++;
        }
        return depth;
    }
}

111.二叉树的最小深度

官方题目链接： 111. 二叉树的最小深度

题目分析

方案一

层序遍历

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int result = 0;

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            result++;
            queue.offer(null);
            int flag = 0;
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);

                if (poll.right != null)
                    queue.offer(poll.right);

                if (poll.left == null && poll.right == null)
                    return result;
            }
            queue.poll();
        }
        return result;
    }
}

结果

解答成功:
执行耗时:2 ms,击败了68.39% 的Java用户
内存消耗:59.9 MB,击败了92.93% 的Java用户

方案二：深度优先搜索

递归好难想

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        return rescur(root);
    }

    private int rescur(TreeNode root) {
        if (root.left == null && root.right == null) return 1;

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;

    }
}

结果

解答成功:
执行耗时:9 ms,击败了33.45% 的Java用户
内存消耗:60.3 MB,击败了71.30% 的Java用户

官方题解

https://leetcode.cn/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码随想录

https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_111-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6

相对于 104.二叉树的最大深度，本题还也可以使用层序遍历的方式来解决，思路是一样的。

需要注意的是，只有当左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

代码实现

class Solution {
    public int minDepth(TreeNode root){
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            depth++;
            TreeNode cur = null;
            for (int i = 0; i < size; i++) {
                cur = queue.poll();
                //如果当前节点的左右孩子都为空，直接返回最小深度
                if (cur.left == null && cur.right == null){
                    return depth;
                }
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
        }
        return depth;
    }
}

226.翻转二叉树（优先掌握递归）※

建议：这道题目一些做过的同学理解的也不够深入，建议大家先看我的视频讲解，无论做过没做过，都会有很大收获。

题目链接： https://leetcode.cn/problems/invert-binary-tree/
文章讲解： https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

题目分析

深度优先搜索：递归遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        recursion(root);
        return root;
    }

    private void recursion(TreeNode root) {
        if (root == null) return;

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

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.6 MB,击败了98.52% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

广度优先搜索：迭代遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Deque<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        while (!queue.isEmpty()) {
            queue.offer(null);

            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                if (poll.left != null)
                    queue.offer(poll.left);
                if (poll.right != null)
                    queue.offer(poll.right);
                swap(poll);
            }
            queue.poll();

        }
        return root;
    }

    private void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39 MB,击败了46.19% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

深度优先搜索：迭代遍历

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //================深度优先搜索：迭代遍历========================
        if (root == null) return root;

        Deque<TreeNode> stack = new LinkedList<>();

        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();

            if (pop.left != null)
                stack.push(pop.left);
            if (pop.right != null)
                stack.push(pop.right);

            swap(pop);
        }
        
        return root;
    }

    private void swap(TreeNode root) {  //================迭代遍历========================
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:38.9 MB,击败了75.39% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

如果要从整个树来看，翻转还真的挺复杂，整个树以中间分割线进行翻转，如图：

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序，前中后序应该选哪一种遍历顺序？（一些同学这道题都过了，但是不知道自己用的是什么顺序）

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！

递归法

以前序遍历为例，通过动画来看一下翻转的过程:

我们来看一下递归三部曲：

确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。
返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*。

1	`TreeNode* invertTree(TreeNode* root)`

确定终止条件

当前节点为空的时候，就返回

1	`if (root == NULL) return root;`

确定单层递归的逻辑

因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树。

1
2
3

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);

代码实现

//DFS递归
class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行，因为先左孩子交换孩子，再根交换孩子（做完后，右孩子已经变成了原来的左孩子），再右孩子交换孩子（此时其实是对原来的左孩子做交换）
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

迭代法

深度优先遍历

https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E8%BF%AD%E4%BB%A3%E6%B3%95

具体代码实现可见上方：深度优先搜索：迭代遍历

广度优先遍历

也就是层序遍历，层数遍历也是可以翻转这棵树的，因为层序遍历也可以把每个节点的左右孩子都翻转一遍

代码实现

//BFS
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) deque.offer(node.left);
                if (node.right != null) deque.offer(node.right);
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

101. 对称二叉树（优先掌握递归）※

建议：

题目链接： https://leetcode.cn/problems/symmetric-tree/
文章讲解： https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

题目分析

递归遍历

发现迭代的难点在于想不明白如何将大问题切分成小问题
递归的三步走套用不上，导致出现回答不上来的问题。

class Solution {
    private boolean FLAG = true;
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        recursion(root.left, root.right);

        return FLAG;
    }

    private void recursion(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null && rightNode == null) return;

        if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
            FLAG = false;
            return;
        }

        recursion(leftNode.left, rightNode.right);
        recursion(leftNode.right, rightNode.left);
        
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.5 MB,击败了76.70% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

迭代遍历

使用了两个队列，对其进行判断时进行了特殊处理，当遇到null的时候也向队列中添加，防止例题中实例2的发生。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        // ============迭代法===================
        TreeNode flagNode = new TreeNode();
        Deque<TreeNode> leftNode = new LinkedList<>();
        Deque<TreeNode> rightNode = new LinkedList<>();

        leftNode.offer(root.left);
        rightNode.offer(root.right);

        while (!leftNode.isEmpty() && !rightNode.isEmpty()) {
            leftNode.offer(flagNode);
            rightNode.offer(flagNode);

            while (leftNode.peek() != flagNode && rightNode.peek() != flagNode) {
                TreeNode leftTem = leftNode.poll();
                TreeNode rightTem = rightNode.poll();

                if (leftTem == null && rightTem == null) continue;
                else if (leftTem == null) return false;
                else if (rightTem == null) return false;
                else if (leftTem.val != rightTem.val) return false;

                leftNode.offer(leftTem.left);
                leftNode.offer(leftTem.right);
                rightNode.offer(rightTem.right);
                rightNode.offer(rightTem.left);

            }
            leftNode.poll();
            rightNode.poll();
        }
        return true;
    }
}

结果

解答成功:
执行耗时:1 ms,击败了20.27% 的Java用户
内存消耗:39.5 MB,击败了79.52% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

代码随想录

https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html

思路

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

那么如何比较呢？

比较的是两个子树的里侧和外侧的元素是否相等。如图所示：

那么遍历的顺序应该是什么样的呢？

本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。

其实后序也可以理解为是一种回溯。

递归法

递归三部曲

确定递归函数的参数和返回值

因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
返回值自然是bool类型。

代码如下：

1	`bool compare(TreeNode* left, TreeNode* right)`

确定终止条件

要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。

节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）

左节点为空，右节点不为空，不对称，return false
左不为空，右为空，不对称 return false
左右都为空，对称，返回true

此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：

左右都不为空，比较节点数值，不相同就return false

此时左右节点不为空，且数值也不相同的情况我们也处理了。

代码如下：

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

注意上面最后一种情况，我没有使用else，而是else if，因为我们把以上情况都排除之后，剩下的就是左右节点都不为空，且数值相同的情况。

确定单层递归的逻辑

此时才进入单层递归的逻辑，单层递归的逻辑就是处理左右节点都不为空，且数值相同的情况。

比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
如果左右都对称就返回true ，有一侧不对称就返回false 。

代码如下：

bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
return isSame;

如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。

代码实现

/**
 * 递归法
 */
public boolean isSymmetric1(TreeNode root) {
    return compare(root.left, root.right);
}

private 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 compareOutside = compare(left.left, right.right);
    // 比较内侧
    boolean compareInside = compare(left.right, right.left);
    return compareOutside && compareInside;
}

迭代法

https://programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E8%BF%AD%E4%BB%A3%E6%B3%95

这道题目我们也可以使用迭代法，但要注意，这里的迭代法可不是前中后序的迭代写法，因为本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前中后序的关系了。

这里我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转，（注意这不是层序遍历）

使用队列

通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等，如动画所示：

如下的条件判断和递归的逻辑是一样的。

使用栈

细心的话，其实可以发现，这个迭代法，其实是把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较，那么其实使用栈也是可以的。

只要把队列原封不动的改成栈就可以了。

代码实现

   /**
     * 迭代法
     * 使用双端队列，相当于两个栈
     */
    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;
    }

    /**
     * 迭代法
     * 使用普通队列
     */
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            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不同
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

100. 相同的树

#未完成

官方题目链接： 100. 相同的树

题目分析

方案一

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

方案二

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

572. 另一棵树的子树

#未完成

官方题目链接： 572. 另一棵树的子树

题目分析

方案一

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

方案二

结果

分析

时间复杂度：
O( )

空间复杂度：
O( )

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

13、第六章二叉树 part02

http://yuanql.top/2023/07/26/02_1_代码随想录算法训练营18期/13、第六章二叉树 part02/

作者

Qingli Yuan

发布于

2023年7月26日

许可协议

2023年7月26日每日一题--2569. 更新数组后处理求和查询上一篇

2023年7月25日每日一题--2208. 将数组和减半的最少操作次数下一篇

13、第六章 二叉树 part02

本节内容

层序遍历※

代码随想录

102.二叉树的层序遍历

题目分析

方案一：迭代遍历

结果

方案二：递归遍历

结果

代码随想录

代码实现

107.二叉树的层次遍历II

题目分析

方案一

结果

代码随想录

代码实现

199.二叉树的右视图

题目分析

方案一

结果

代码随想录

代码实现

637.二叉树的层平均值

题目分析

方案一：广度优先搜索：层序遍历

结果

方案二：深度优先搜索

结果

官方题解

代码随想录

代码实现

429.N叉树的层序遍历

题目分析

方案一

结果

代码随想录

代码实现

515.在每个树行中找最大值

题目分析

方案一

结果

方案二： 深度优先搜索

结果

官方题解

代码随想录

代码实现

116.填充每个节点的下一个右侧节点指针

题目分析

方案一：层序遍历

结果

方案二：使用已建立的 nextnext 指针

结果

官方题解

代码随想录

代码实现

117.填充每个节点的下一个右侧节点指针II

题目分析

方案一

结果

代码随想录

代码实现

104.二叉树的最大深度

题目分析

方案一：层序遍历

结果

方案二：迭代遍历

结果

代码随想录

代码实现

111.二叉树的最小深度

题目分析

方案一

结果

方案二：深度优先搜索

结果

官方题解

代码随想录

代码实现

13、第六章二叉树 part02

方案二：深度优先搜索

226.翻转二叉树（优先掌握递归）※

101. 对称二叉树（优先掌握递归）※