题解 | #二叉树的中序遍历#

NC161 二叉树的中序遍历

题意

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

1. 递归法

所谓中序遍历，就是先中序遍历左子树，在访问遍历树根，然后中序遍历右子树。

把上面的汉字翻译成代码，用一个全局变量维护遍历路径即可。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> res;

    void dfs(TreeNode* p) {
        if (!p) 
            return;
        dfs(p->left);
        res.push_back(p->val);
        dfs(p->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
};

时间复杂度： $O(n)$ , 遍历一轮树上的所有节点。
空间复杂度： $O(n)$ ，定义了一个长度为 $n$ 的数组。

2. 非递归法

方法一显然太简单了，不是面试官想要的，那么我们分析下如何非递归实现。

函数调用的本质就是栈，只是计算机底层已经帮我们实现了压栈退栈，所以我们自己实现栈，用栈来模拟递归的过程。看上面递归的代码，思考下整体执行的过程：

一直执行dfs(left), 直到左子树为空
执行最后一层的res.push_back(p->val);;
执行最后一层的dfs(right),进入了新的一层递归，然后回到步骤1.

因此我们自己来实现，思路如下：

根节点入栈；模拟dfs(root)开始执行，设指针p表示当前dfs函数的参数，初始化为root
如果p不空，就一直往左走到头，直到为空（模拟一直调用dfs(p->left)压栈）
p=栈顶元素，（模拟p=空节点的父节点时，那一层dfs执行完dfs(p->left)退出后的动作）
p指向p的右孩子，模拟dfs(p->right).
回到第2步，直到栈为空或者p为空。

用一张图描述上述过程：
图片说明

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 *    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;

        if (!root) return res;
        stack<TreeNode*> s; // 定义一个栈

        auto p = root; // p从根节点开展，模拟最开头的dfs(root)
        while (p || !s.empty()) {
            // 一直往左走，等价于dfs(left)
            while (p) {
                s.push(p);
                p = p->left;
            }

            p = s.top(); // 弹栈，表示执行到一层非空的dfs，参数为p
            s.pop();

            res.push_back(p->val); // 执行p->val
            p = p->right; // 执行dfs(right), 改变参数p
        }
        return res;
    }
};

时间复杂度： $O(n)$ , 遍历一轮树上的所有节点。
空间复杂度： $O(n)$ ，定义了一个长度为 $n$ 的栈