二叉树前中后序遍历总结
1. 三种遍历顺序
- 前序遍历：根 -> 左 -> 右
- 中序遍历：左 -> 根 -> 右
- 后序遍历：左 -> 右 -> 根
记忆：
- 前序：根最先
- 中序：根在中间
- 后序：根最后
2. LeetCode 144：二叉树前序遍历
递归写法
package leetcode202604.day20;
import treenode.TreeNode;
import java.util.ArrayList;
import java.util.List;
public class Problem144 {
/**
* 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
*
* @param root 二叉树
* @return 前序遍历
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val); // 根
preorder(node.left, result); // 左
preorder(node.right, result); // 右
}
}
思路
前序遍历就是：
先访问根节点
再遍历左子树
最后遍历右子树
也就是：
根 -> 左 -> 右
3. 前中后序递归模板
前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
private void preorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val); // 根
preorder(node.left, result); // 左
preorder(node.right, result); // 右
}
中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorder(node.left, result); // 左
result.add(node.val); // 根
inorder(node.right, result); // 右
}
后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorder(root, result);
return result;
}
private void postorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
postorder(node.left, result); // 左
postorder(node.right, result); // 右
result.add(node.val); // 根
}
4. 统一理解
三种遍历本质上都是同一个递归框架，区别只是：
处理当前节点的位置不同
统一模板：
private void traverse(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
// 前序位置
traverse(node.left, result);
// 中序位置
traverse(node.right, result);
// 后序位置
}
可以这样理解：
- 前序：
result.add(node.val)放在最前面 - 中序：
result.add(node.val)放在左递归和右递归之间 - 后序：
result.add(node.val)放在最后面
5. 前序遍历的非递归写法
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
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;
}
为什么先压右，再压左？
因为栈是：
后进先出
想让左子树先处理，就必须先把右子树压进去。
6. 常见易错点
1）忘记判空
if (node == null) {
return;
}
2）顺序写错
前序：根左右
中序：左根右
后序：左右根
3）前序非递归压栈顺序写反
前序想得到的是：
根 -> 左 -> 右
所以必须：
先压右，再压左
7. 背诵版
前序：根左右
中序：左根右
后序：左右根