36-二叉树的中序遍历

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

递归遍历和非递归遍历应该牢牢背熟。

递归遍历

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

非递归遍历

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

Morris 中序遍历

Morris 遍历算法可以将非递归的中序遍历空间复杂度降为$O(1)$。

假设当前遍历节点为x，步骤为：

1. 如果 x 无左孩子，加入答案数组，接着访问x右孩子
2. 如果 x 有左孩子，就找到 x 左子树上最右的节点(即 左子树中序遍历的最后一个节点，x在中序遍历中的前驱节点)，记为 predecessor。根据predecessor的右孩子是否为空，进行操作：
   • 如果predecessor的右孩子为空，则将右孩子指向x，然后访问x的左孩子
   • 如果右孩子不为空，则该右孩子一定指向x(因为predecessor一定是x的左子树的最右节点，所以若右孩子不为空则一定是指向x)，这是说明已遍历完x的左子树，那么就将predecessor的右孩子置空，将x加入答案数组，然后访问x的右孩子

重复操作，直至遍历完整棵树。

在整个过程，其实多做了一步：假设当前遍历到节点为x，将x的左子树的最右节点指向x，这样当左子树遍历完后就通过这个指向走回x，且通过这个指向可以知道已经遍历完了左子树，不需要栈来维护。

class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode * p = root;
        while (p) {
            if(p->left) {
                TreeNode * predecessor = p->left;
                while (predecessor->right && predecessor->right != p) {
                    predecessor = predecessor->right;
                }
                if(predecessor->right == nullptr) {
                    predecessor->right = p;
                    p = p->left;
                } else {
                    predecessor->right = nullptr;
                    res.push_back(p->val);
                    p = p->right;
                }
            } else {
                res.push_back(p->val);
                p = p->right;
            }
        }

        return res;
    }
};

性能分析

时间复杂度：每个节点都访问了两个，所以为$O(n)$。

空间复杂度：$O(1)$。

颜色标记法

来自评论。

算法思想

中序遍历，即每个节点在第二次访问的时候会被输出。因此可以使用任何东西来记录节点的访问次数，当第二次被访问的时候就输出。

因此可以使用颜色，或者使用哈希表来记录。

用白色表示从未被访问过的节点，用灰色表示已被访问过一次。

则：

1. 当访问到的节点为白色时，则标记为灰色，然后依次将它的右子结点，它自己，左子结点 进栈
2. 如果访问到的节点为灰色时，则添加到答案数组中，即输出

初始时，将根节点标记为白色，然后进栈。

然后循环出栈即可。

这种方式可以对于前序、后序、中序写出一致的代码。

注意

因为前序遍历顺序为：中 左 右

中序遍历顺序为：左 中 右

后序遍历顺序为：左 右 中

而栈是先进后出，所以中序遍历时，反过来，加入栈的顺序是：右子结点、自己、左子结点。

同样，如果是 前序遍历那么加入栈的顺序应为：右子结点、左子结点、自己。

算法实现

class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<pair<TreeNode *, int>> s;
        s.push(make_pair(root, 0)); //0代表白色节点，1代表灰色节点
        while (!s.empty()) {
            pair<TreeNode *, int> node = s.top();
            s.pop();
            if(node.first == nullptr) {
                continue;
            }
            if(node.second == 0) {
                s.push(make_pair(node.first->right, 0));
                s.push(make_pair(node.first,1));
                s.push(make_pair(node.first->left, 0));
            } else {
                res.emplace_back(node.first->val);
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。