二叉树基础
二叉树基础
二叉树结构定义
在 LeetCode 中是这样定义二叉树的节点的：
▼java复制代码public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { this.val = x; } }
后续讨论都基于这一结构展开。
遍历二叉树
二叉树的遍历方式通常可以分为深度优先遍历（DFS）和广度优先遍历（BFS）。
深度优先遍历包括前序遍历、中序遍历和后序遍历；广度优先遍历通常指层序遍历。
递归遍历
方法声明：void traverse(TreeNode root);
输入：二叉树的根节点。
职责：遍历以 root 为根的二叉树。
递归终止条件：root 为 null 时，无需继续遍历。
要完整地遍历一棵二叉树，需要以下几个步骤：
- 处理当前节点
- 遍历左子树
- 遍历右子树
对于当前节点而言，遍历左子树和遍历右子树就是两个规模更小的子问题，而这两个子问题都可以交给同一个 traverse 方法解决。
综上所述，可以梳理出如下代码：
▼java复制代码void traverse(TreeNode root){ if(root == null){ return; } traverse(root.left); traverse(root.right); }
这样，随着递归不断深入，二叉树中的每一个节点都会作为 traverse 方法的参数被访问。
此时，我没有在代码中写出【处理当前节点】这一步骤。实际上，我们可以在以下三个位置处理当前节点：
▼java复制代码void traverse(TreeNode root){ if(root == null){ return; } // ① traverse(root.left); // ② traverse(root.right); // ③ }
①、②、③ 三个位置分别对应前序遍历、中序遍历和后序遍历。
接下来，你可以尝试完成以下题目来巩固这些遍历方式：
层序遍历
层序遍历是指，从二叉树根节点所在的层开始，按照从上往下、从左往右的顺序处理二叉树中的节点。例如：
要实现这种遍历方式，往往需要借助队列这一数据结构，它用于存储待处理的二叉树节点。
一开始，根节点先入队。
然后我们从队列中取出元素进行处理。
当前节点处理完毕后，如果它存在左孩子，就将左孩子入队；如果存在右孩子，就将右孩子入队。仔细观察可以发现：当前层节点出队时，我们会将它们的孩子依次入队，而这些孩子恰好构成下一层待处理的节点。
对于每个节点，我们都按照“先左后右”的顺序将孩子入队。由于队列具有 FIFO 的特点，先入队的节点会先被处理，因此最终就能保证节点按照“从上往下、从左往右”的顺序被访问。
综上所述，可以梳理出如下代码：
▼java复制代码void levelOrder(TreeNode root){ // 边界条件 if(root == null){ return; } Queue<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode treeNode = queue.poll(); System.out.println(treeNode.val); // 将这个节点的左右孩子依次入队 if(treeNode.left != null){ queue.offer(treeNode.left); } if(treeNode.right != null){ queue.offer(treeNode.right); } } }
上面的代码只能按照层序遍历的顺序依次访问每个节点，接下来请你先去看一道题：102. 二叉树的层序遍历。
题目要求我们收集每一层的遍历结果，可是队列中不断有新节点入队，我们怎么知道什么时候某一层遍历结束了？
关键在于，我们不能一直无条件地从队列中取出节点，而是要精确控制当前层需要取出的节点数量。当前层有多少个节点，我们就从队列中取出多少次节点。
请你再手动模拟一遍层序遍历，我需要你重点观察在开始处理某一层之前，queue.size()有什么规律？
不难发现，在开始处理某一层之前，队列中恰好存放着这一层尚未处理的所有节点，因此此时的 queue.size() 就等于当前层的节点数。
于是我们可以对先前的代码进行如下改造：
▼java复制代码void levelOrder(TreeNode root){ // 边界条件 if(root == null){ return; } Queue<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()){ int curLevelSize = queue.size(); for (int i = 0; i < curLevelSize; i++) { TreeNode treeNode = queue.poll(); System.out.println(treeNode.val); if(treeNode.left != null){ queue.offer(treeNode.left); } if(treeNode.right != null){ queue.offer(treeNode.right); } } } }
虽然处理当前层的过程中，还会不断将下一层节点加入队列，但 curLevelSize 已经提前记录了当前层的节点数量，因此 for 循环只会处理当前层的节点。
理解这一点之后，如何收集每一层的遍历结果，相信你也可以自己解决，接下来请去解决这道 leetcode 题目吧！
