⭐️ 题目日期：

字节 - 2025/1/4，小米 - 2024/10/10，百度 - 2024/8/13

🌳 题目描述：

二叉树的遍历分为：

• 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。

• 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。

• 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

记忆小技巧：

前序，中序，后序说的是根节点何时遍历；前序：根节点先；中序：根节点“居中”；后序：根节点最后；

左节点始终先于右节点

实现二叉树的遍历通常有两种方法：递归和迭代，下面我们分别看看这两种方法。

1. 使用递归法实现二叉树的遍历

如图所示，二叉树的前序遍历，即（根左右），得到的遍历顺序为：12，5，3，7，15，13，20；中序遍历（左根右），得到的遍历顺序为：3，5，7，12，13，15，20；后序遍历（左右根），得到的顺序为：3，7，5，13，20，15，12

🕵🏽 面试评估：

这道题考察二叉树的遍历方式，即前中后序的递归遍历方式，主要考察候选者能否有效地运用递归思维，将其与二叉树的结构特点结合，完成不同遍历方式的实现。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

用递归的方法完成树的遍历，递归的本质是分解问题，将复杂问题分解为更小的相同问题。

二叉树的遍历天然适合递归，因为：

• 每棵树都可以分解为根节点 + 左子树 + 右子树。
• 遍历过程可以通过递归调用对子树进行相同的处理。

1. 前序遍历

   前序遍历的顺序为 根左右，那么先访问根节点，然后递归访问左子树，最后递归访问右子树。

💻代码(Java、Python)：

Java

public void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " "); // 也可以使用相应的数据结构进行存储，这里我们选择打印
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

Python

def pre_order_traversal(root):
    if root is None:
        return

    print(root.val, end=" ")  # 也可以使用相应的数据结构进行存储，这里我们选择打印
    pre_order_traversal(root.left)
    pre_order_traversal(root.right)

2. 中序遍历

   中序遍历的顺序为 左根右，那么先递归访问左子树，然后访问根节点，最后递归访问右子树。

💻代码(Java、Python)：

Java

public void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderTraversal(root.left);
    System.out.print(root.val + " "); // 也可以使用相应的数据结构进行存储，这里我们选择打印
    inOrderTraversal(root.right);
}

Python

def in_order_traversal(root):
    if root is None:
        return

    in_order_traversal(root.left)
    print(root.val, end=" ")  # 也可以使用相应的数据结构进行存储，这里我们选择打印
    in_order_traversal(root.right)

3. 后序遍历

   后序遍历的顺序为 左右根，那么先递归访问左子树，然后递归访问右子树，最后访问根节点。

💻代码(Java、Python)：

Java

public void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.print(root.val + " "); // 也可以使用相应的数据结构进行存储，这里我们选择打印
}

Python

def post_order_traversal(root):
    if root is None:
        return

    post_order_traversal(root.left)
    post_order_traversal(root.right)
    print(root.val, end=" ")  # 也可以使用相应的数据结构进行存储，这里我们选择打印

2. 使用迭代法实现二叉树的遍历（必须掌握，面试题型）

🕵🏽 面试评估：

这道题考察二叉树的迭代法遍历，要求候选人结合栈的使用根据不同遍历的顺序来存储和访问相应的节点。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

用迭代的方法完成树的遍历需基于以下两点：

• 基于栈模拟递归：递归实现树的遍历本质上是利用了函数调用栈。当采用迭代方法时，使用栈数据结构来模拟函数调用栈的行为。因为栈具有后进先出（LIFO）的特性，这与递归过程中函数调用和返回的顺序相匹配。
• 对节点访问顺序的控制：在遍历过程中，根据前序、中序、后序遍历各自对节点访问顺序的要求，通过调整节点进栈和出栈的顺序来实现不同的遍历方式。

1. 前序遍历

迭代解法基本步骤：

• 首先将根节点压入栈中。
• 当栈不为空时，执行以下操作：
  • 弹出栈顶元素，访问该元素（将该元素存储至List）。
  • 先将右子节点压入栈（如果存在），再将左子节点压入栈（如果存在）。这样保证在弹出时先处理左子树再处理右子树。

图解如下：

💻代码(Java、Python)：

Java

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

    Deque<TreeNode> stack = new LinkedList<>();
    stack.offerLast(root);

    while (!stack.isEmpty()) {
        TreeNode current = stack.pollLast();
        result.add(current.val);

        if (current.right!= null) {
            stack.offerLast(current.right);
        }
        if (current.left != null) {
            stack.offerLast(current.left);
        }
    }

    return result;
}

Python

    def preorderTraversal(self, root):
        result = []
        if root is None:
            return result

        stack = [root]

        while stack:
            current = stack.pop()
            result.append(current.val)

            if current.right:
                stack.append(current.right)
            if current.left:
                stack.append(current.left)
        
        return result

2. 中序遍历

迭代解法基本步骤：

• 从根节点开始，将当前节点以及其所有左子节点依次压入栈中。
• 当前节点不为空或者栈不为空时：
  • 弹出栈顶元素，访问该元素。
  • 将当前节点设置为弹出节点的右子节点，然后重复将当前节点及其左子节点压入栈的操作。

图解：

💻代码(Java、Python)：

Java

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.offerLast(current);
                current = current.left;
            } else {
                current = stack.pollLast();
                result.add(current.val);
                current = current.right;
            }
        }
        return result;
    }

Python

    def inorderTraversal(self, root):
        result = []
        stack = []
        current = root
    
        while current is not None or stack:
            if current is not None:
                stack.append(current)
                current = current.left
            else:
                current = stack.pop()
                result.append(current.val)
                current = current.right
    
        return result

3. 后序遍历

迭代解法基本步骤：

• 将根节点压入栈中。
• 当栈不为空时：
  • 查看栈顶元素，如果该元素满足以下三种情况之一，将其从栈中弹出并存储：
    • 该元素左右子树为空
    • 该元素从左子树返回 （这里无需考虑当前元素有无右子树，若无，容易理解，访问完左子树，再访问当前节点；若有，则之前该元素的左右子树均已压入栈中：当前 ｜ 右节点 ｜ 左节点，不存在从左节点直接回到当前节点，因为中间有右节点需要访问，最终会从右节点返回。这里也证明，直接从左节点回来的，当前节点无右节点）
    • 该元素从右子树返回
  • 若不满足以上的条件，说明还有其他节点需要先遍历，分别将右节点（若有），左节点（若有）压入栈中

图解

💻代码(Java、Python)：

Java

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

        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode current = root;
        TreeNode pre = null;
        stack.offerLast(current);

        while (!stack.isEmpty()) {
            current = stack.peekLast();
            if ((current.left == null && current.right == null) ||
                    (pre != null && pre == current.left) ||
                    (pre != null && pre == current.right)) {
                result.add(current.val);
                stack.pollLast();
                pre = current;
            } else {
                if (current.right != null) {
                    stack.offerLast(current.right);
                }
                if (current.left != null) {
                    stack.offerLast(current.left);
                }
            }
        }

        return result;
    }

Python

    def postorderTraversal(self, root):
        result = []
        if root is None:
            return result
    
        stack = []
        current = root
        pre = None
        stack.append(current)
    
        while stack:
            current = stack[-1]
    
            if (current.left is None and current.right is None) or (pre is not None and (pre == current.left or pre == current.right)):
                result.append(current.val)
                stack.pop()
                pre = current
            else:
                if current.right is not None:
                    stack.append(current.right)
                if current.left is not None:
                    stack.append(current.left)
    
    
        return result

🚵🏻复杂度分析：

两种方法的前中后序遍历的时间复杂度和空间复杂度相同，为

时间复杂度：O(n)，n 为节点个数

空间复杂度：O(h)，h 为树的高度，为栈的空间；如果我们需要存储节点或者节点的值到数组或者List, 则空间复杂度为O(n)

🔬在线评测(Online Judge):

前序遍历： 题目链接

中序遍历： 题目链接

后序遍历： 题目链接