Easy

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历的节点值。

示例 1：

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

输出：[1,3,2]

示例 2：

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

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

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

约束条件：

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

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

解题思路

中序遍历是按照"左子树 → 根节点 → 右子树"的顺序访问二叉树的所有节点。本题有两种经典解法：

方法一：递归解法

这是最直观的解法。对于每个节点，我们先递归遍历它的左子树，然后访问当前节点，最后递归遍历右子树。递归的终止条件是遇到空节点。

方法二：迭代解法（推荐）

使用栈来模拟递归过程。我们从根节点开始，不断将当前节点的左子节点入栈，直到左子节点为空。然后弹出栈顶节点并访问，接着转向该节点的右子树，重复这个过程。

迭代解法的优势在于：

  1. 避免了递归可能导致的栈溢出问题
  2. 空间复杂度在最坏情况下仍为 O(h)，但实际运行时更稳定
  3. 更符合题目进阶要求

两种方法的时间复杂度都是 O(n)，空间复杂度都是 O(h)，其中 h 是树的高度。

代码实现

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* current = root;
        
        while (current != nullptr || !st.empty()) {
            // 将左子树全部入栈
            while (current != nullptr) {
                st.push(current);
                current = current->left;
            }
            
            // 访问当前节点
            current = st.top();
            st.pop();
            result.push_back(current->val);
            
            // 转向右子树
            current = current->right;
        }
        
        return result;
    }
};

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        current = root
        
        while current or stack:
            # 将左子树全部入栈
            while current:
                stack.append(current)
                current = current.left
            
            # 访问当前节点
            current = stack.pop()
            result.append(current.val)
            
            # 转向右子树
            current = current.right
        
        return result

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) {
        IList<int> result = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode current = root;
        
        while (current != null || stack.Count > 0) {
            // 将左子树全部入栈
            while (current != null) {
                stack.Push(current);
                current = current.left;
            }
            
            // 访问当前节点
            current = stack.Pop();
            result.Add(current.val);
            
            // 转向右子树
            current = current.right;
        }
        
        return result;
    }
}

var inorderTraversal = function(root) {
    const result = [];
    const stack = [];
    let current = root;
    
    while (current !== null || stack.length > 0) {
        // 将左子树全部入栈
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }
        
        // 访问当前节点
        current = stack.pop();
        result.push(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
递归解法O(n)O(h)
迭代解法O(n)O(h)

其中 n 是二叉树中节点的个数，h 是二叉树的高度。在最坏情况下（完全倾斜的树），h = n，空间复杂度为 O(n)。在最好情况下（完全平衡的树），h = log n，空间复杂度为 O(log n)。

相关题目