94.二叉树中序遍历 (Medium)*

题目描述*

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

示例*

输入: [1,null,2,3]

输出: [1,3,2]

进阶*

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

代码*

最简单的就是递归。

栈的思路：每遇到一个结点 A，先将 A 入栈，遍历左子树，接着访问 A，最后遍历右子树。访问完 A 后，A 就可以出栈了，因为 A 与其左子树都已经访问完成。

Mirros Traversal 算法：

递归和栈的方法都是使用了 O(h) 的辅助空间来保存上一层的信息，中序遍历就是遍历完左子树然后遍历根节点。左子树最后遍历的结点一定是叶子结点（实际就是中序遍历下根结点的前驱），我们把它的右指针指向根节点，这样就不需要额外的空间，遍历完左子树，就可以回到根结点。

具体的步骤：

cur->left == nullptr，保存 cur 的值，更新 cur = cur->right。
cur->left != nullptr，找到 cur->left 这个子树最右结点记为 last。
1. last->right == nullptr，则 last->right = cur，更新 cur = cur->left。
2. last->right != nullptr，说明之前已经访问过，表明当前子树已访问完成，保存 cur 的值，更新 cur = cur->right。

递归栈Mirros Traversal

class Solution {
public:
    void helper(TreeNode *root, vector<int>& res) {
        if(root != nullptr) {
            helper(root->left, res);
            res.push_back(root->val);
            helper(root->right, res);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> helpStack;
        TreeNode *cur = root;
        while(cur != nullptr || !helpStack.empty()) {
            while(cur != nullptr) {
                helpStack.push(cur);
                cur = cur->left;
            }
            cur = helpStack.top();
            helpStack.pop();
            res.push_back(cur->val);
            cur = cur->right;
        }
        return res;
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *cur = root;
        while(cur != nullptr) {
            if(cur->left == nullptr) {
                res.push_back(cur->val);
                cur = cur->right;
            }else {
                TreeNode *last = cur->left;
                // 找到左子树最右结点
                while(last->right != nullptr && last->right != cur) {
                    last = last->right;
                }
                if(last->right == nullptr) {
                    last->right = cur;
                    cur = cur->left;
                }else if(last->right == cur) {
                    last->right = nullptr;
                    res.push_back(cur->val);
                    cur = cur->right;
                }
            }
        }
        return res;
    }
};

最后更新: July 23, 2022