达到O(1)空间复杂度同时时间复杂度仍保持O(n)的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    TreeNode *pre = nullptr, *cur = root;
    while(cur) {
        if (cur->left) pre = cur->left;
        else {
               res.emplace_back(cur->val);
            cur = cur->right;
            continue;
        }
        while(pre->right && pre->right != cur) pre = pre->right;
        if (pre->right) {
            pre->right = nullptr;
            res.emplace_back(cur->val);
               cur = cur->right;
           } else {
            pre->right = cur;
               cur = cur->left;
           }
    }
    return res;
}

cur指针为当前状态，从root开始，pre指针将移至cur左子树的最右节点，并将其right指针指向cur,然后cur左移 ，不断重复上述操作直至cur移至left为空的节点（这是中序遍历的起点），读取该节点的值（此处为加入vector容器），并让cur右移。假若原树中该节点right指空，那么前述操作已将其指为其父节点；若非空，那么循环继续。

整个算法的抽象概括就是将原本入栈的中节点放入其左子树的最右处的right指针，已Node来代替栈空间开销，从而实现O(1)的空间复杂度。

特别的，整个过程不可避免地会改变原树结构，若需在遍历后还原，需在cur“读栈”时将左子树的最右节点的right重新指空以恢复原结构。