力扣94题：二叉树的中序遍历, 解题思路和步骤解析

问题描述

力扣第94题要求我们实现一个函数，该函数能够对给定的二叉树进行中序遍历，并返回遍历结果的列表。中序遍历是一种树遍历方式，其顺序为：先遍历左子树，访问根节点，遍历右子树。

解题思路分析

解决这个问题，我们可以考虑两种主要方法：递归和迭代。递归方法直观且易于实现，但可能会导致栈溢出的问题，特别是在处理深度很大的树时。迭代方法则需要使用栈来模拟递归过程，能够有效避免栈溢出的问题。

递归方法实现

递归方法的核心思想是先递归遍历左子树，访问根节点，递归遍历右子树。这种方法的代码实现简洁，但需要注意递归深度。

class Solution {
public:
    vectorinorderTraversal(TreeNode root) {
        vectorresult;
        helper(root, result);
        return result;
    }
    
    void helper(TreeNode node, vector& result) {
        if (!node) return;
        helper(node->left, result);
        result.push_back(node->val);
        helper(node->right, result);
    }
};

迭代方法实现

迭代方法使用栈来模拟递归过程，通过循环和条件判断来控制遍历顺序。这种方法能够有效避免递归导致的栈溢出问题，适用于处理大型数据。

class Solution {
public:
    vectorinorderTraversal(TreeNode root) {
        vectorresult;
        stacks;
        TreeNode cur = root;
        
        while (cur || !s.empty()) {
            while (cur) {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top(); s.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }
        return result;
    }
};