一、二叉树的递归遍历
二叉树的总共有三种遍历，分别是前序，中序，后序
前序遍历的顺序是：中，左，右
中序遍历的顺序是：左，中，右
后序遍历的顺序是：左，右，中
以图中二叉树为例，它的三种遍历结果分别为：
前序：123456
中序：321546
后序：325641
再比如：
例题：
前序遍历：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
示例 5：
输入：root = [1,null,2] 输出：[1,2]
代码：
首先定义二叉树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}前序遍历
//定义方法和参数
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val); // 将当前节点的值加入到结果列表中
preorder(root.left, result); // 递归遍历左子树
preorder(root.right, result); // 递归遍历右子树
}- 方法是实际执行前序遍历的递归函数。它接受两个参数：
root表示当前要遍历的节点，result是存储遍历结果的列表。 - 如果当前节点
root为null，表示遍历到叶子节点的空子节点，直接返回。 - 否则，将当前节点的值
root.val添加到result列表中。 - 然后递归调用
preorder方法，先遍历左子树root.left，再遍历右子树root.right。
中序遍历：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
代码：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
public void inorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
inorder(root.left, result);
result.add(root.val);
inorder(root.right, result);
}同理
后序遍历：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
代码
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
public void postorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
postorder(root.left, result);
postorder(root.right, result);
result.add(root.val);
}三种遍历方式代码基本相同，只需要将顺序稍加修改
二、二叉树的非递归遍历
非递归遍历，即为迭代的方式去遍历二叉树，我们采用栈来对元素进行存储
前序遍历：
由于前序遍历的顺序是：中，左，右，为了用栈来实现这样的顺序，需要我们先将根节点压入栈中，然后弹出，表示遍历的第一个节点
随后遍历根节点的左右节点，这里由于栈先进后出的特性，在遍历时应该先压入右节点再压入左节点，这样在弹出时才能保证前序遍历的顺序
然后依次遍历左右孩子的孩子节点，重复上述操作，直到所有节点遍历完毕
当栈中的所有元素均弹出后，说明遍历解释，得到的结果数组即为前序遍历
代码
//前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>(); // 用于存储前序遍历结果的列表
if (root == null) {
return result; // 如果根节点为空，直接返回空的结果列表
}
Stack<TreeNode> stack = new Stack<>(); // 辅助用栈进行迭代遍历
stack.push(root); // 将根节点压入栈中作为起始点
while (!stack.isEmpty()) {
TreeNode node = stack.pop(); // 弹出栈顶的节点
result.add(node.val); // 将节点的值添加到结果列表中，实现前序遍历
// 注意：由于栈是先入后出的结构，因此先压入右子节点再压入左子节点，保证左子树先于右子树被访问
if (node.right != null) {
stack.push(node.right); // 如果有右子节点，则压入栈中
}
if (node.left != null) {
stack.push(node.left); // 如果有左子节点，则压入栈中
}
}
return result; // 返回前序遍历的结果列表
}
- 创建一个空的
ArrayList对象result，用来存储遍历结果。 - 如果根节点
root为null，直接返回空的result列表。 - 否则，创建一个
Stack对象stack，用来辅助进行迭代遍历。将根节点root推入栈中作为起始点。 - 使用
while循环来迭代执行以下操作，直到栈为空：- 弹出栈顶的节点
node，并将其值node.val添加到result列表中，实现前序遍历的访问顺序。 - 如果
node的右子节点node.right不为null，则将右子节点压入栈中，因为前序遍历先处理左子树，再处理右子树。 - 如果
node的左子节点node.left不为null，同样将左子节点压入栈中，确保左子树先于右子树被访问。
- 弹出栈顶的节点
后序遍历：
后序遍历与前序遍历大致相同，由于前序遍历的顺序是：中，左，右，而后序遍历的顺序是：左，右，中，我们只需要将前序遍历的顺序变为 （中，右，左） 即交换访问左右节点的顺序，然后将整个结果数组进行翻转，得到的结果即为后序遍历（左，右，中）
代码
//后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>(); // 用于存储后序遍历结果的列表
if (root == null) {
return result; // 如果根节点为空，直接返回空的结果列表
}
Stack<TreeNode> stack = new Stack<>(); // 辅助用栈进行迭代遍历
stack.push(root); // 将根节点压入栈中作为起始点
while (!stack.isEmpty()) {
TreeNode node = stack.pop(); // 弹出栈顶的节点
result.add(node.val); // 将节点的值添加到结果列表中，实现逆后序遍历
// 注意：与前序遍历不同，后序遍历的顺序是左子树 -> 右子树 -> 根节点
// 因此，需要先压入左子节点再压入右子节点，以保证栈顶元素是要处理的节点
if (node.left != null) {
stack.push(node.left); // 如果有左子节点，则压入栈中
}
if (node.right != null) {
stack.push(node.right); // 如果有右子节点，则压入栈中
}
}
Collections.reverse(result); // 最后翻转结果列表，得到后序遍历的顺序
return result; // 返回后序遍历的结果列表
}
中序遍历：
与前序和后序遍历不同的是，由于中序遍历的顺序是左，中，右，在遍历第一个跟节点后，紧接着就是其按其左子树一层一层往下访问的最左端的左节点，因此不能像前后序遍历那样，因此在处理中序遍历时就需要借助指针来帮助访问节点，栈用来处理节点上的元素
过程：
首先压入根节点和其左子树以及一层一层向下的左节点
弹出最后的那个左节点和其父节点，遍历其右节点
继续返回，当根节点的左子树均遍历完全，返回弹出根节点，并压入其右节点
重复上述步骤，直到所有节点均遍历完全
代码
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>(); // 用于存储中序遍历结果的列表
if (root == null) {
return result; // 如果根节点为空，直接返回空的结果列表
}
Stack<TreeNode> stack = new Stack<>(); // 辅助用栈进行迭代遍历
TreeNode cur = root; // cur指针从根节点开始
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur); // 将当前节点压入栈中
cur = cur.left; // 移动到当前节点的左子节点，继续向左遍历
} else {
cur = stack.pop(); // 当前节点为空时，弹出栈顶节点，即最左下角的节点
result.add(cur.val); // 将节点值加入结果列表，实现中序遍历的顺序
cur = cur.right; // 移动到当前节点的右子节点，继续遍历右子树
}
}
return result; // 返回中序遍历的结果列表
}
- 创建一个
ArrayList类型的result对象，用于存储中序遍历的结果。 - 如果根节点
root为null，直接返回空的result列表。 - 创建一个
Stack对象stack，用于辅助迭代遍历二叉树。同时初始化cur指针为根节点root。 - 使用
while循环迭代执行以下操作，直到cur为null且栈为空：- 如果
cur不为null，将当前节点cur压入栈中，并将cur移动到其左子节点cur.left，继续向左遍历。 - 如果
cur为null，说明当前节点没有左子节点或者左子树已经遍历完毕，此时弹出栈顶节点cur = stack.pop()，将节点值cur.val加入result列表，然后将cur移动到其右子节点cur.right，继续遍历右子树。
- 如果
今天的学习就到这里了
