LeetCode 144 二叉树前序遍历：递归、迭代、Morris三种解法

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序遍历 。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1图片

输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：

示例2图片

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]

示例 3：

输入：root = []
输出：[]

示例 4：

输入：root = [1]
输出：[1]

提示

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

解题思路

方法一：递归

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。递归实现很直观。

关键点：

递归的终止条件是空节点
按照前序遍历的顺序访问节点
用列表存储遍历结果

具体步骤：

当前节点为空就返回
把当前节点的值加入结果列表
递归遍历左子树
递归遍历右子树

时间复杂度：O(n)，n 是二叉树的节点数，每个节点遍历一次。空间复杂度：O(h)，h 是二叉树的高度，递归调用栈的开销。

方法二：迭代（用栈模拟）

用栈模拟递归过程，实现非递归的前序遍历。

关键点：

用栈存储待访问的节点
先将右子节点入栈，再将左子节点入栈（保证先访问左边）
注意入栈顺序

具体步骤：

创建栈，把根节点入栈
栈不为空时循环：
- 弹出栈顶节点并访问
- 右子节点入栈（如果存在）
- 左子节点入栈（如果存在）

时间复杂度：O(n)，n 是节点数，每个节点访问一次。空间复杂度：O(h)，h 是树高，栈的开销。

方法三：Morris遍历（空间O(1)）

Morris遍历可以实现O(1)空间复杂度。这个方法比较巧妙，利用了叶子节点的空指针。

关键点：

利用树的空闲指针（叶子节点的左右指针为空）
不用额外栈空间
遍历时临时修改树结构，最后恢复

具体步骤：

当前节点的左子节点为空时，访问当前节点，然后遍历右子节点
当前节点的左子节点不为空时，找到左子树的最右节点：
- 最右节点的右指针为空，就将其指向当前节点，访问当前节点，然后遍历左子节点
- 最右节点的右指针指向当前节点，说明已经访问过了，重置为空，然后遍历右子节点

时间复杂度：O(n) 空间复杂度：O(1)，这是这个方法的优势

图解思路

递归遍历分析

以示例1为例：root = [1,null,2,3]

遍历过程：

访问根节点1
递归左子树（空）
递归右子树
- 访问节点2
- 递归左子树（节点3）
- 递归右子树（空）

最终输出：[1,2,3]

以示例2为例：root = [1,2,3,4,5,null,8,null,null,6,7,9]

这是一个更复杂的树，前序遍历顺序：根->左->右

先访问根节点1
然后遍历左子树：2->4->5->6->7
最后遍历右子树：3->8->9

最终输出：[1,2,4,5,6,7,3,8,9]

迭代遍历分析

以示例1为例：

步骤	栈的内容	输出数组	说明
初始状态	[1]	[]	将根节点1入栈
第1步	[2]	[1]	弹出并访问1，将2入栈
第2步	[3]	[1,2]	弹出并访问2，将3入栈
第3步	[]	[1,2,3]	弹出并访问3

代码实现

C# 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    // 递归方法
    public IList<int> PreorderTraversal(TreeNode root) {
        List<int> result = new List<int>();
        PreorderHelper(root, result);
        return result;
    }
    
    private void PreorderHelper(TreeNode node, List<int> result) {
        if (node == null) {
            return;
        }
        
        result.Add(node.val);
        PreorderHelper(node.left, result);
        PreorderHelper(node.right, result);
    }
    
    // 迭代方法
    public IList<int> PreorderTraversalIterative(TreeNode root) {
        List<int> result = new List<int>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            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;
    }
}

Python 实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 递归方法
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def preorder(node: TreeNode, result: List[int]):
            if not node:
                return
            result.append(node.val)
            preorder(node.left, result)
            preorder(node.right, result)
        
        result = []
        preorder(root, result)
        return result
    
    # 迭代方法
    def preorderTraversalIterative(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        
        return result

C++ 实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归方法
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        preorderHelper(root, result);
        return result;
    }
    
private:
    void preorderHelper(TreeNode* node, vector<int>& result) {
        if (!node) {
            return;
        }
        
        result.push_back(node->val);
        preorderHelper(node->left, result);
        preorderHelper(node->right, result);
    }
    
public:
    // 迭代方法
    vector<int> preorderTraversalIterative(TreeNode* root) {
        vector<int> result;
        if (!root) {
            return result;
        }
        
        stack<TreeNode*> st;
        st.push(root);
        
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            
            if (node->right) {
                st.push(node->right);
            }
            if (node->left) {
                st.push(node->left);
            }
        }
        
        return result;
    }
};

性能分析

各语言的性能对比：

实现语言	执行用时	内存消耗
C++	0 ms	8.3 MB
Python	32 ms	15.7 MB
C#	92 ms	39.8 MB

C++性能最好，Python代码最简洁。

补充说明

代码亮点

提供了三种实现方式，从简单到优化
迭代方法中利用栈的特性（先右后左入栈）
Morris遍历实现了空间O(1)

常见错误

忘记处理空树
迭代时入栈顺序错了（应该先右后左）
递归时忘记传递结果列表

讨论

有几个问题可以思考一下：

Morris遍历虽然空间复杂度是O(1)，但实际面试中用得多吗？
三种方法（递归、迭代、Morris）你觉得哪个最容易理解？
如果要在遍历过程中修改树的结构，应该用哪种方法？

欢迎在评论区讨论。

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。

题目描述

难度

题目链接

示例

示例 1：

示例 2：

示例 3：

示例 4：

提示

解题思路

方法一：递归

方法二：迭代（用栈模拟）

方法三：Morris遍历（空间O(1)）

图解思路

递归遍历分析

迭代遍历分析

代码实现

C# 实现

Python 实现

C++ 实现

性能分析

补充说明

代码亮点

常见错误

相关题目

讨论