二叉树的遍历、构造与线索化

00 | 概述

二叉树的基本操作包括建立、遍历、复制以及结构修改等。在线索二叉树中，还可以利用原本为空的指针记录节点的前驱与后继，从而减少遍历过程中对递归和栈的依赖。

本文从二叉链表出发，依次介绍二叉树的非递归遍历、广义表建树、结构复制与修改，以及前序、中序、后序线索化的实现。

01 | 二叉树的遍历

1. 基本概念

二叉树的深度优先遍历分为前序、中序和后序三种，其区别在于根节点的访问时机。

考虑下面这棵二叉树：

遍历方式	访问顺序	遍历结果
前序遍历	根 → 左 → 右	1 2 4 5 3 6
中序遍历	左 → 根 → 右	4 2 5 1 3 6
后序遍历	左 → 右 → 根	4 5 2 6 3 1

三种遍历均可以递归实现。以前序遍历为例：

void preorder(TreeNode* root) {
    if (root == nullptr) return;

    visit(root);
    preorder(root->left);
    preorder(root->right);
}

中序、后序遍历只需调整 visit(root) 的位置。

递归调用依赖系统栈保存尚未完成的函数状态。对于包含 $n$ 个节点、高度为 $h$ 的二叉树，三种递归遍历的时间复杂度均为 $O (n)$ ，递归栈空间复杂度为 $O (h)$ 。

2. 非递归前序遍历

参考：LeetCode 144. 二叉树的前序遍历

题目要求返回二叉树的前序遍历序列，并尝试使用非递归算法实现。

前序遍历要求先访问根节点，再访问左子树，最后访问右子树。

沿左子树向下访问时，需要保存尚未访问的右子树。利用栈存储这些右孩子，即可完成非递归遍历。

算法过程：

访问当前节点。
如果存在右孩子，将其压栈。
进入左子树。
左子树访问结束后，从栈中取出尚未访问的右子树。
重复上述过程，直到所有节点均被访问。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;

    TreeNode* p = root;

    while (p || !stk.empty()) {
        if (p) {
            ans.push_back(p->val);

            if (p->right)
                stk.push(p->right);

            p = p->left;
        } else {
            p = stk.top();
            stk.pop();
        }
    }

    return ans;
}

考虑：

访问节点 1 时，先将右孩子 3 入栈，再进入左子树 2。

访问节点 2 时，将右孩子 5 入栈，再进入节点 4。

此时栈的状态为：

栈顶 → 5
       3

节点 4 没有左孩子，因此弹出 5。访问完节点 5 后，再弹出 3。

最终得到：

1 \to 2 \to 4 \to 5 \to 3

这里的栈只保存尚未访问的右子树根节点，不需要保存所有经过的节点。

3. 非递归中序遍历

参考：LeetCode 94. 二叉树的中序遍历

中序遍历要求先访问左子树，再访问根节点，最后访问右子树。

因此，进入左子树之前，需要将当前节点压栈。等左子树访问结束，再从栈中取出当前节点进行访问。

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;

    TreeNode* p = root;

    while (p || !stk.empty()) {
        if (p) {
            stk.push(p);
            p = p->left;
        } else {
            p = stk.top();
            stk.pop();

            ans.push_back(p->val);
            p = p->right;
        }
    }

    return ans;
}

算法不断沿左孩子向下，同时保存途中经过的节点。到达最左节点后，依次访问栈顶节点及其右子树。

与前序遍历相比，中序遍历需要保留尚未访问的祖先节点，因此栈中保存的是沿左子树下降时经过的节点。

4. 非递归后序遍历

参考：LeetCode 145. 二叉树的后序遍历

后序遍历要求先访问左右子树，最后访问根节点。

一个节点从栈顶取出时，其左子树已经处理完毕，但右子树可能尚未访问。因此，需要判断右子树是否已经完成。

使用 last 保存上一个访问完成的节点：

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> stk;

    TreeNode* p = root;
    TreeNode* last = nullptr;

    while (p || !stk.empty()) {
        if (p) {
            stk.push(p);
            p = p->left;
        } else {
            TreeNode* cur = stk.top();

            if (cur->right && last != cur->right) {
                p = cur->right;
            } else {
                ans.push_back(cur->val);
                last = cur;
                stk.pop();
            }
        }
    }

    return ans;
}

核心判断为：

if (cur->right && last != cur->right)

如果当前节点存在右孩子，且右子树尚未遍历完毕，就需要先进入右子树。

否则，可以访问当前节点并将其出栈。

为什么可以通过 last == cur->right 判断右子树是否遍历完成？

后序遍历总是最后访问子树的根节点。右子树遍历结束时，最后访问的节点恰好是当前节点的右孩子。因此，只需比较 last 与右孩子的地址。

三种非递归遍历均只访问每个节点常数次，时间复杂度为 $O (n)$ ，辅助空间复杂度为 $O (h)$ 。

02 | 二叉树的建立与表示

1. 广义表表示法

二叉树可以使用广义表表示。

例如：

A(B(D,E),C(F,G))

表示：

        A
       / \
      B   C
     / \ / \
    D  E F  G

其中：

A 表示节点。
( 表示开始描述当前节点的孩子。
, 分隔左子树和右子树。
) 表示当前节点的孩子描述结束。

空子树可以省略对应位置的节点。

例如：

A(B(,D),C)

表示：

在 B(,D) 中，逗号前没有节点，说明 B 的左孩子为空，右孩子为 D。

2. 根据广义表建立二叉树

考虑以下问题：

给定一个合法的广义表字符串 s，其中每个节点的值都是一个大写英文字母，构造对应的二叉链表并返回根节点。

函数接口：

TreeNode* createTree(const string& s);

这里使用字符型节点：

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(char x)
        : val(x), left(nullptr), right(nullptr) {}
};

扫描字符串时，需要知道当前节点应该连接到哪个父节点，以及它是父节点的左孩子还是右孩子。

可以使用栈保存父节点，并使用标志位 flag 区分左右子树。

约定：

flag = 1：接下来建立左孩子。
flag = 2：接下来建立右孩子。

扫描规则如下：

字符	操作
`(`	当前节点入栈，准备建立左子树
`,`	开始建立右子树
`)`	当前子树结束，父节点出栈
字母	创建节点并连接到栈顶父节点

实现：

TreeNode* createTree(const string& s) {
    stack<TreeNode*> stk;

    TreeNode* root = nullptr;
    TreeNode* cur = nullptr;

    int flag = 0;

    for (char c : s) {
        switch (c) {
            case '(':
                stk.push(cur);
                flag = 1;
                break;

            case ',':
                flag = 2;
                break;

            case ')':
                stk.pop();
                break;

            default:
                cur = new TreeNode(c);

                if (root == nullptr) {
                    root = cur;
                } else if (flag == 1) {
                    stk.top()->left = cur;
                } else {
                    stk.top()->right = cur;
                }
        }
    }

    return root;
}

栈顶始终保存当前正在建立孩子的父节点。

当遇到嵌套括号时，新的父节点入栈；对应子树结束后，父节点出栈，恢复上一层的构造过程。

对于包含 $n$ 个字符的合法广义表，扫描每个字符只需要常数时间，因此总时间复杂度为 $O (n)$ 。栈中最多保存一条从根到当前节点的路径，辅助空间复杂度为 $O (h)$ 。

类似题目：LeetCode 536. 从字符串生成二叉树

需要注意，LeetCode 536 使用另一种括号表示法：

4(2(3)(1))(6(5))

没有使用逗号，而是通过连续的两组括号区分左右子树。解析思路类似，具体语法需要分别处理。

3. 根据二叉树创建字符串

参考：LeetCode 606. 根据二叉树创建字符串

这道题要求按照前序遍历，将二叉树转换成带括号的字符串。

例如：

输出：

1(2()(4))(3)

括号的保留规则如下：

如果左右孩子均为空，省略括号。
如果只有左孩子，省略表示空右孩子的括号。
如果只有右孩子，必须保留表示空左孩子的 ()。

第三条保证了字符串可以正确反映二叉树结构。

例如：

    1
     \
      2

必须表示为：

1()(2)

如果写成 1(2)，就无法区分节点 2 是左孩子还是右孩子。

使用递归实现：

class Solution {
public:
    string tree2str(TreeNode* root) {
        if (root == nullptr) return "";

        string ans = to_string(root->val);

        if (!root->left && !root->right)
            return ans;

        ans += "(";
        ans += tree2str(root->left);
        ans += ")";

        if (root->right) {
            ans += "(";
            ans += tree2str(root->right);
            ans += ")";
        }

        return ans;
    }
};

这里有几个需要注意的细节。

首先，整数应使用 to_string() 转换：

ans += to_string(root->val);

如果使用：

ans += static_cast<char>(root->val + '0');

只能正确处理 0 到 9 的单个数字，无法正确处理多位整数和负数。

其次，叶子节点应该返回已经构造的字符串：

if (!root->left && !root->right)
    return ans;

直接返回空字符串会导致只有一个节点的二叉树无法正确输出。

另外，这里使用局部变量 ans，使每次递归调用都独立生成当前子树对应的字符串。

如果将 ans 定义为类的成员变量，递归调用就会共享同一份字符串。虽然也能实现，但需要额外处理多次调用时的初始化问题。

03 | 二叉树的复制与结构修改

1. 二叉树的深拷贝

考虑一个使用二叉链表存储节点的 BinaryTree 类。

复制构造函数通常写为：

BinaryTree(const BinaryTree& other) {
    root = copy(other.root);
}

这里的 copy() 是辅助函数，负责递归复制整棵二叉树。

如果直接执行：

root = other.root;

两个对象将共享同一棵二叉树：

t1.root ──┐
          ├──> 同一棵二叉树
t2.root ──┘

修改其中一个对象中的节点，将影响另一个对象。

如果两个对象都负责释放节点，还可能出现重复释放的问题。

因此，需要重新分配节点并复制整棵树。

TreeNode* copy(const TreeNode* root) {
    if (root == nullptr)
        return nullptr;

    TreeNode* node = new TreeNode(root->val);

    node->left = copy(root->left);
    node->right = copy(root->right);

    return node;
}

复制过程按照以下顺序执行：

创建当前节点的副本。
递归复制左子树。
递归复制右子树。

每个节点都拥有独立的内存地址，完成深拷贝。

对于包含 $n$ 个节点、高度为 $h$ 的二叉树，复制时间复杂度为 $O (n)$ ，递归栈空间复杂度为 $O (h)$ ，新建二叉树本身占用 $O (n)$ 空间。

如果类负责管理动态分配的节点，还需要正确实现析构函数和复制赋值运算符，避免内存泄漏或重复释放。

2. 将二叉树展开为链表

参考：LeetCode 114. 二叉树展开为链表

给定二叉树的根节点 root，要求按照前序遍历顺序，将整棵树原地展开为单链表。

展开后：

所有节点的左孩子均为 nullptr。
每个节点的右指针指向前序遍历中的下一个节点。

例如：

展开后：

1 → 2 → 3 → 4 → 5 → 6

一种思路是保存前序遍历中的上一个节点 prev。

每次访问当前节点时，将前驱节点的右指针连接到当前节点：

prev->left = nullptr;
prev->right = root;
prev = root;

但这个过程会修改原来的二叉树结构。

例如：

        1
       / \
      2   5

访问节点 2 时，如果直接执行：

prev->right = root;

就会将节点 1 的右指针从 5 改成 2。

如果后续仍然依靠原来的 1->right 访问右子树，就会丢失节点 5 的访问路径。

因此，需要在修改指针之前保存原来的左右孩子。

class Solution {
private:
    TreeNode* prev = nullptr;

    void dfs(TreeNode* root) {
        if (root == nullptr) return;

        TreeNode* left = root->left;
        TreeNode* right = root->right;

        if (prev != nullptr) {
            prev->left = nullptr;
            prev->right = root;
        }

        prev = root;

        dfs(left);
        dfs(right);
    }

public:
    void flatten(TreeNode* root) {
        prev = nullptr;
        dfs(root);
    }
};

这样，递归过程始终沿着保存的原始孩子指针进行。

另外，prev 是类的成员变量，每次调用 flatten() 时都需要重新初始化，避免不同调用之间共享旧状态。

算法访问每个节点一次，时间复杂度为 $O (n)$ ，递归栈空间复杂度为 $O (h)$ 。

类似的指针修改问题还会出现在二叉树的线索化过程中。

04 | 线索二叉树

1. 引入

普通二叉链表中的每个节点包含两个孩子指针：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

对于包含 $n$ 个节点的非空二叉树，共有 $2 n$ 个孩子指针域。

由于一棵包含 $n$ 个节点的树恰好有 $n - 1$ 条边，因此非空孩子指针的数量为 $n - 1$ 。

空指针的数量为：

2 n - (n - 1) = n + 1

这些空指针可以用于保存节点在某种遍历序列中的前驱和后继。

例如：

        A
       / \
      B   C

中序遍历序列为：

B \to A \to C

节点 B 的右孩子为空，因此可以将其右指针指向节点 A，表示 B 的中序后继。

节点 C 的左孩子为空，因此可以将其左指针指向节点 A，表示 C 的中序前驱。

这种利用空指针保存遍历关系的二叉树称为线索二叉树（Threaded Binary Tree）。

2. 节点结构

线索化之后，左右指针可能指向孩子，也可能指向遍历前驱或后继。

因此，需要增加标志位区分指针的用途。

struct TreeNode {
    int val;

    TreeNode* left;
    TreeNode* right;

    bool ltag;
    bool rtag;

    TreeNode(int x)
        : val(x),
          left(nullptr),
          right(nullptr),
          ltag(false),
          rtag(false) {}
};

标志位含义如下：

标志位	值	指针含义
`ltag`	`false`	左孩子
`ltag`	`true`	遍历前驱
`rtag`	`false`	右孩子
`rtag`	`true`	遍历后继

线索化时，只修改原本为空的孩子指针，原有的孩子关系保持不变。

需要注意，前驱和后继取决于遍历顺序。同一个节点在前序、中序、后序遍历中的前驱和后继可能不同。

3. 线索化的基本思想

无论采用哪种遍历顺序，线索化都可以使用一个指针 pre 保存上一个访问的节点。

假设当前访问节点为 current。

如果当前节点没有左孩子，可以将左指针改为指向前驱：

if (current->left == nullptr) {
    current->left = pre;
    current->ltag = true;
}

如果上一个节点没有右孩子，可以将其右指针指向当前节点：

if (pre != nullptr && pre->right == nullptr) {
    pre->right = current;
    pre->rtag = true;
}

最后更新：

pre = current;

为什么可以在访问当前节点时确定上一个节点的后继？

因为 pre 和 current 是遍历序列中连续访问的两个节点。当前节点恰好是上一个节点的后继。

因此，每次访问新节点时，都可以同时处理当前节点的前驱线索和上一个节点的后继线索。

三种线索化算法都遵循这一规则，区别在于当前节点的处理时机。

05 | 中序线索化

1. 中序线索化算法

中序遍历顺序为：

左子树 \to 根节点 \to 右子树

因此，先递归处理左子树，再建立当前节点的线索，最后递归处理右子树。

void inorderThread(TreeNode* current, TreeNode*& pre) {
    if (current == nullptr) return;

    inorderThread(current->left, pre);

    if (current->left == nullptr) {
        current->left = pre;
        current->ltag = true;
    }

    if (pre != nullptr && pre->right == nullptr) {
        pre->right = current;
        pre->rtag = true;
    }

    pre = current;

    inorderThread(current->right, pre);
}

其中，pre 使用引用传递，保证所有递归调用共享同一个前驱指针。

调用时，需要初始化 pre：

void inorderThread(TreeNode* root) {
    TreeNode* pre = nullptr;

    inorderThread(root, pre);

    if (pre != nullptr && pre->right == nullptr)
        pre->rtag = true;
}

这里需要考虑遍历序列中的最后一个节点。

由于它没有后继，如果原来的右孩子为空，应将其右指针保留为 nullptr，同时设置 rtag = true。

另外，空树时 pre 始终为 nullptr，不能直接执行：

pre->right = nullptr;

必须先判断 pre 是否为空。

2. 利用中序线索遍历

中序线索化完成之后，可以不使用递归和栈进行中序遍历。

首先找到中序序列中的第一个节点，即二叉树最左边的节点。

TreeNode* p = root;

while (p && p->left && !p->ltag)
    p = p->left;

之后，每次访问当前节点，都需要寻找它的中序后继。

分为两种情况：

rtag == true：右指针指向中序后继，直接沿线索移动。
rtag == false：右指针指向右孩子，中序后继是右子树中最左边的节点。

完整实现：

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;

    TreeNode* p = root;

    while (p && p->left && !p->ltag)
        p = p->left;

    while (p) {
        ans.push_back(p->val);

        if (p->rtag) {
            p = p->right;
        } else {
            p = p->right;

            while (p && p->left && !p->ltag)
                p = p->left;
        }
    }

    return ans;
}

3. 判断线索的时机

考虑：

中序遍历序列为：

4 \to 2 \to 5 \to 1

节点 4 的右线索指向节点 2。

访问节点 4 后，如果先执行：

p = p->right;

此时 p 已经指向节点 2。

如果随后检查：

if (!p->rtag)

判断的就是节点 2 的右指针类型。

由于节点 2 有真实右孩子，其 rtag == false，程序可能误以为刚刚进入了某棵右子树，于是沿节点 2 的左孩子返回节点 4，造成重复访问。

因此，应当先根据当前节点的 rtag 判断右指针的用途，再决定如何移动。

还有一个需要注意的地方：

p = p->right;

执行后，p 可能变为 nullptr。如果随后立即访问 p->rtag 或 p->val，就会发生空指针解引用。

4. 复杂度

对于包含 $n$ 个节点、高度为 $h$ 的二叉树：

中序线索化：

T (n) = O (n), S (n) = O (h)

利用线索进行中序遍历：

T (n) = O (n), S (n) = O (1)

这里的辅助空间复杂度不计存储遍历结果的数组。

虽然寻找中序后继时，可能需要沿真实左孩子指针连续下降，但每个节点只会被访问有限次，因此总时间复杂度仍然为 $O (n)$ 。

06 | 前序线索化

1. 前序线索化算法

前序遍历顺序为：

根节点 \to 左子树 \to 右子树

因此，需要先处理当前节点，再递归处理左右子树。

根据前面的线索建立规则，可以写出：

void preorderThread(TreeNode* current, TreeNode*& pre) {
    if (current == nullptr) return;

    if (current->left == nullptr) {
        current->left = pre;
        current->ltag = true;
    }

    if (pre != nullptr && pre->right == nullptr) {
        pre->right = current;
        pre->rtag = true;
    }

    pre = current;

    preorderThread(current->left, pre);
    preorderThread(current->right, pre);
}

但这段代码存在问题。

2. 递归过程中修改指针

考虑：

    A
   /
  B

初始状态：

A.left → B
B.left → nullptr

按照前序遍历，先访问节点 A，再访问节点 B。

处理 B 时，由于它没有左孩子，执行：

B->left = A;
B->ltag = true;

此时：

B.left → A

如果随后继续执行：

preorderThread(B->left, pre);

就会重新访问节点 A。

这样可能产生重复访问，甚至无限递归。

前序线索化是在递归访问子树之前修改节点指针，因此需要根据标志位判断当前指针是否仍然指向真实孩子。

修改为：

if (!current->ltag)
    preorderThread(current->left, pre);

if (!current->rtag)
    preorderThread(current->right, pre);

完整实现：

void preorderThread(TreeNode* current, TreeNode*& pre) {
    if (current == nullptr) return;

    if (current->left == nullptr) {
        current->left = pre;
        current->ltag = true;
    }

    if (pre != nullptr && pre->right == nullptr) {
        pre->right = current;
        pre->rtag = true;
    }

    pre = current;

    if (!current->ltag)
        preorderThread(current->left, pre);

    if (!current->rtag)
        preorderThread(current->right, pre);
}

调用：

void preorderThread(TreeNode* root) {
    TreeNode* pre = nullptr;

    preorderThread(root, pre);

    if (pre != nullptr && pre->right == nullptr)
        pre->rtag = true;
}

也可以在修改指针之前保存原来的左右孩子，再沿保存的指针递归。

这与前面二叉树展开为链表时的处理方式类似。

3. 利用前序线索遍历

前序线索化完成之后，遍历过程相对简单。

访问当前节点后：

如果存在真实左孩子，进入左子树。
否则沿右指针移动。

这里的右指针可能指向真实右孩子，也可能指向前序后继。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ans;

    TreeNode* p = root;

    while (p) {
        ans.push_back(p->val);

        if (!p->ltag)
            p = p->left;
        else
            p = p->right;
    }

    return ans;
}

考虑：

前序遍历序列为：

1 \to 2 \to 4 \to 5 \to 3

节点 4 没有真实左孩子，其右线索指向后继节点 5。

节点 5 同样没有真实左孩子，可以继续沿右线索访问节点 3。

因此，无需使用栈保存尚未访问的右子树。

前序线索遍历的时间复杂度为 $O (n)$ ，辅助空间复杂度为 $O (1)$ 。

07 | 后序线索化

1. 后序线索化算法

后序遍历顺序为：

左子树 \to 右子树 \to 根节点

因此，先递归处理左右子树，最后建立当前节点的线索。

void postorderThread(TreeNode* current, TreeNode*& pre) {
    if (current == nullptr) return;

    postorderThread(current->left, pre);
    postorderThread(current->right, pre);

    if (current->left == nullptr) {
        current->left = pre;
        current->ltag = true;
    }

    if (pre != nullptr && pre->right == nullptr) {
        pre->right = current;
        pre->rtag = true;
    }

    pre = current;
}

调用：

void postorderThread(TreeNode* root) {
    TreeNode* pre = nullptr;

    postorderThread(root, pre);

    if (pre != nullptr && pre->right == nullptr)
        pre->rtag = true;
}

后序线索化的实现比较直接，但利用线索完成后序遍历要复杂一些。

2. 后序线索遍历的困难

考虑：

后序遍历序列为：

4 \to 5 \to 2 \to 3 \to 1

节点 4 没有右孩子，因此可以将它的右指针改为指向后继节点 5。

节点 5 没有右孩子，其右线索可以指向节点 2。

但节点 2 已经存在真实右孩子 5，所以它的右指针必须保留，无法用来保存后序后继 3。

因此，仅依靠普通的后序线索，不能像中序线索遍历那样方便地找到所有节点的后继。

一种解决方式是在节点结构中增加 parent 指针。

struct TreeNode {
    int val;

    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;

    bool ltag;
    bool rtag;

    TreeNode(int x)
        : val(x),
          left(nullptr),
          right(nullptr),
          parent(nullptr),
          ltag(false),
          rtag(false) {}
};

其中，parent 指向当前节点的双亲。

建立普通二叉树时，同时维护 parent：

parent->left = child;
child->parent = parent;

右孩子同理。

线索化过程中不需要修改 parent。

3. 寻找第一个后序节点

后序遍历优先访问左子树，其次访问右子树，最后访问根节点。

因此，寻找一棵子树的第一个后序节点时，需要按照以下规则不断下降：

如果存在真实左孩子，进入左子树。
否则，如果存在真实右孩子，进入右子树。
如果没有真实孩子，当前节点就是第一个后序节点。

TreeNode* firstPost(TreeNode* root) {
    TreeNode* p = root;

    while (p) {
        if (!p->ltag && p->left) {
            p = p->left;
        } else if (!p->rtag && p->right) {
            p = p->right;
        } else {
            break;
        }
    }

    return p;
}

这里必须在每次移动之后重新判断当前节点的左右孩子。

例如：

正确的后序遍历序列为：

3 \to 2 \to 1

从根节点 1 出发，先进入右孩子 2，随后必须进入节点 2 的左孩子 3。

如果直接沿右孩子一路向下，就会遗漏节点 3。

4. 寻找后序后继

假设当前节点为 p，需要寻找它的后序后继。

首先检查：

p->rtag

如果 rtag == true，说明右指针指向后序后继，可以直接移动：

p = p->right;

如果 rtag == false，说明右指针指向真实右孩子，需要借助 parent 判断。

令：

TreeNode* q = p->parent;

分为以下情况。

情况一：p 是双亲的右孩子。

访问完右子树后，下一个节点就是双亲：

p = q;

情况二：p 是双亲的左孩子，且双亲没有真实右孩子。

同样可以直接访问双亲。

情况三：p 是双亲的左孩子，且双亲存在真实右孩子。

此时需要先访问双亲的右子树：

p = firstPost(q->right);

如果当前节点是整棵树的根节点，则不存在后序后继，遍历结束。

将上述规则组合起来：

if (p->rtag) {
    p = p->right;
} else {
    TreeNode* q = p->parent;

    if (q == nullptr) {
        p = nullptr;
    } else if (q->right == p || q->rtag) {
        p = q;
    } else {
        p = firstPost(q->right);
    }
}

5. 完整的后序线索遍历

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;

    TreeNode* p = firstPost(root);

    while (p) {
        ans.push_back(p->val);

        if (p->rtag) {
            p = p->right;
        } else {
            TreeNode* q = p->parent;

            if (q == nullptr) {
                p = nullptr;
            } else if (q->right == p || q->rtag) {
                p = q;
            } else {
                p = firstPost(q->right);
            }
        }
    }

    return ans;
}

整个遍历过程没有使用递归和栈。

其中，firstPost() 用于寻找一棵尚未访问的子树中的第一个后序节点。每次进入这样的子树，都沿真实孩子指针向下移动，直到找到首个需要访问的节点。

在完整遍历过程中，这些下降操作不会反复扫描已经处理过的子树，因此总时间复杂度仍为 $O (n)$ 。

辅助空间复杂度为 $O (1)$ ，不计存储遍历结果的数组，也不计二叉树本身增加的 parent 指针。

08 | 三种线索二叉树的比较

1. 线索化顺序

三种线索化算法的核心处理过程完全相同：

if (current->left == nullptr) {
    current->left = pre;
    current->ltag = true;
}

if (pre != nullptr && pre->right == nullptr) {
    pre->right = current;
    pre->rtag = true;
}

pre = current;

区别在于这一过程相对于左右子树递归的位置。

类型	处理顺序
前序线索化	处理当前节点 → 左子树 → 右子树
中序线索化	左子树 → 处理当前节点 → 右子树
后序线索化	左子树 → 右子树 → 处理当前节点

前序线索化在递归之前就会修改当前节点的指针，因此需要检查 ltag 和 rtag，防止沿新建立的线索继续递归。

中序和后序线索化的递归调用已经先完成相应子树的处理，不会在上述实现中沿新建立的线索重复访问。

2. 线索遍历

类型	寻找后继的方法
前序线索二叉树	优先进入左子树，否则沿右指针移动
中序线索二叉树	有右线索则直接访问后继，否则寻找右子树最左节点
后序线索二叉树	优先利用右线索，必要时通过双亲寻找后继

前序和中序线索遍历可以直接利用孩子指针与线索完成。

后序线索遍历相对复杂，因为节点的右指针可能需要保留真实右孩子，无法同时保存后序后继。

增加 parent 指针后，可以利用双亲关系完成非递归、无栈的后序遍历。

3. 复杂度

设二叉树有 $n$ 个节点，高度为 $h$ 。

操作	时间复杂度	辅助空间复杂度
前序线索化（递归）	$O (n)$	$O (h)$
中序线索化（递归）	$O (n)$	$O (h)$
后序线索化（递归）	$O (n)$	$O (h)$
前序线索遍历	$O (n)$	$O (1)$
中序线索遍历	$O (n)$	$O (1)$
后序线索遍历（含 `parent`）	$O (n)$	$O (1)$

需要区分线索化阶段和线索遍历阶段。

递归线索化仍然需要 $O (h)$ 的递归栈空间。完成线索化后，才可以利用已经建立的指针关系，在常数辅助空间内完成遍历。

09 | 实现中的几个细节

1. 不能重复线索化

线索化完成后，部分空指针已经指向前驱或后继。

如果再次使用普通的递归线索化算法，就可能沿着这些线索访问已经处理过的节点，造成重复访问甚至无限递归。

因此，本文的线索化函数均假设输入是一棵尚未线索化的普通二叉树。

2. 必须区分孩子指针与线索

在线索二叉树中：

if (p->left)
    p = p->left;

无法保证进入的是真实左子树。

正确的判断应该结合标志位：

if (p->left && !p->ltag)
    p = p->left;

右孩子同理。

3. 注意空指针解引用

例如：

p = p->right;
cout << p->val;

如果 p->right == nullptr，第二行就会访问空指针。

线索化后的首尾节点尤其需要注意这一点。遍历序列中的第一个节点没有前驱，最后一个节点没有后继，对应线索可能指向 nullptr。

4. 修改结构前保存必要信息

原地展开二叉树、前序线索化等操作，都需要在遍历过程中修改节点指针。

如果后续访问仍然依赖原来的孩子关系，就必须提前保存原始指针，或者利用标志位保证只沿真实孩子指针移动。

5. 检验线索结构不能只检查遍历结果

普通递归遍历同样可以得到正确的前序、中序或后序序列。

因此，验证线索化算法时，还应检查：

原有孩子指针是否保留。
原本为空的指针是否正确建立线索。
ltag 和 rtag 是否正确。
前驱、后继是否符合指定的遍历顺序。

一种直接的方法是在线索化之前保存各节点的原始左右孩子指针，以及对应的遍历序列。

线索化完成后，根据原始结构逐个检查所有节点的指针与标志位。

10 | 总结

二叉树的构造、遍历与线索化，可以从遍历顺序和指针关系两个方面理解。

递归遍历通过函数调用栈保存尚未完成的访问过程。非递归遍历则需要显式维护这些信息，通常使用栈保存待访问的节点。

线索化进一步利用二叉链表中的空指针保存遍历序列中的前驱、后继，使后续遍历可以减少对辅助存储的依赖。

在实现层面，最需要注意的是遍历过程中对指针的修改。原本指向孩子的路径一旦被改写，后续访问就必须重新确认指针的含义。

前序、中序、后序线索化使用相同的前驱、后继建立规则，只需根据遍历顺序调整当前节点的处理时机。

掌握这些关系之后，三种线索化算法都可以直接从对应的遍历过程推导出来。

题目	主要内容
LeetCode 144. 二叉树的前序遍历	非递归前序遍历
LeetCode 94. 二叉树的中序遍历	非递归中序遍历
LeetCode 145. 二叉树的后序遍历	非递归后序遍历
LeetCode 536. 从字符串生成二叉树	字符串解析与建树
LeetCode 606. 根据二叉树创建字符串	二叉树的字符串表示
LeetCode 114. 二叉树展开为链表	遍历与原地修改指针
C语言网 1698. 线索二叉树	中序线索化与遍历