03-树3 Tree Traversals Again - 中国大学MOOC-陈越、何钦铭-数据结构-2024春季 (pintia.cn)

先序和中序顺序的推导

众所周知，先序是先访问根节点的，因此在题目给出的建树顺序下（先根-后左-再右），所有 push 操作创建根节点的顺序就是先序遍历的顺序。 （注意一个细节，这里的左右指的是遍历它的所有子树，直到叶子结点） 那么再推中序遍历的顺序，由于堆栈过程中一直到底然后再出栈，明显的是中序遍历顺序。 所以根据堆栈操作，可以推知的是树的先序和中序顺序。

由先序和中序顺序推导后序遍历顺序

首先通过先序确定根节点，然后再中序中确定根节点的位置。 两者的区间分别用四个指针维护。

void dfs(int pl,int pr,int il, int ir){
    if(pl > pr)
        return;
    int root = pre[pl];
    int p = distance(in.begin(),find(in.begin(),in.end(),root));

    int len = p - il;// 子树的长度
    dfs(pl+1,pl+len,il,p-1);// 划定当前根节点下的左子树节点（先序、中序遍历顺序）
    dfs(pl+len+1,pr,p+1,ir);// 右子树
    post.push_back(root);
}

明确一点，叶子节点可以看做没有后继节点的根节点，所以这最后三行的处理顺序也就代表了对树节点的访问顺序。 其实这里面每一步都是一样的，确定当前根节点，中序找根节点，向下加深。

回溯条件推导

至于回溯的条件，当序列中只剩下一个元素，比如

$$[\begin{array}{c}B[C]D\\ [C]BD\end{array}]$$

此时如果再加深搜索的话，会触发回溯条件，推导过程： 要证回溯条件满足 $p_l>p_r$，即证是否存在某些情况，$p_l+1>p_l+len$，化简即 $len<1$ 的情况，显然是有的，那就是根节点取在中序边界左边界时候的情况。 中序遍历顺序中，根节点都在中间，上述情况唯一可能就是中序元素为 1 的情况，也就是说，当搜到叶子节点的时候，那俩 dfs 的递归调用是被打断的，叶子结点则记入数组。