2022.2.18 LeetCode —— 二叉树

文章目录

• 一、今日刷题
• • 1. 第七部分：二叉树 — 102. 二叉树的层序遍历
  • 2. 第七部分：二叉树 — 107. 二叉树的层序遍历 II
  • 3. 第七部分：二叉树 — 199. 二叉树的右视图
  • 4. 第七部分：二叉树 — 637. 二叉树的层平均值
  • 5. 第七部分：二叉树 — 429. N 叉树的层序遍历
• 二、知识积累
• • 1.队列Queue的一些方法：

一、今日刷题

1. 第七部分：二叉树 – 102. 二叉树的层序遍历

跳转LeetCode

答案代码：

维护一个队列用于存储树的节点，一个集合用于存储每层遍历到的节点，对队列的操作很巧妙：
一层一层的遍历，
①先加入第一层的 root 节点到队列中，poll 到集合中，再将集合加入 ans
②将 root 的左右子节点（如果不为 null ）加入队列，分别再 poll 到集合中，再将集合加入 ans
③再陆续将上一层所有节点的左右子节点加入队列，分别再 poll 到集合中，再将集合加入 ans
…
直到队列中没有元素，树的节点也就遍历完了。

package BinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: LYZ
 * @date: 2022/2/18 19:49
 * @description: 105.
 */
public class LevelOrder {
   
    public static void main(String[] args) {
   
        TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        LevelOrder levelOrder = new LevelOrder();
        List<List<Integer>> ans = levelOrder.levelOrder(root);
        System.out.println(ans);
    }

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
   
            List<Integer> level = new ArrayList<>();
            int levelSize = queue.size(); //做题时差了这个语句，结果就不对了
            for (int i = 1; i <= levelSize; i++) {
   
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
   
                    queue.offer(node.left);
                }
                if (node.right != null) {
   
                    queue.offer(node.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

2. 第七部分：二叉树 – 107. 二叉树的层序遍历 II

跳转LeetCode

答案代码：

方法一：
自底向上的层序遍历，我的思路是：整体代码按照自顶向下编写，但引入一个栈，将每一层遍历的节点所存储的集合 level 存入栈，最后利用栈先入后出的原则将元素依次 pop 存入 ans 中。

方法二：
在105题代码最终 return 语句前写

Collections.reverse(ans);

package