题解 | #重建二叉树#

重建二叉树

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

充分说明了本质：前序是“根”的排序，即按最“根”来排序；中序是“左”的排序，即按最“左”来排序。
而这两者具有“部分矛盾性”（左根和根左），从前序的角度来描述，即：

矛盾不发生时（互不打扰时）：前序正在进行根左。

矛盾发生时（同时进行时）：根左和左根是矛盾点，只能寻找相容点，那就是“根-右”或“左-右”。

利用这个“部分矛盾性”，可以区分是左子结点，还是右子结点或左右兄弟（这两者可合在一起考虑）的情况。

构建树，就是构建根和左右子树的关系。

步骤如下：

从前序遍历的结果出发，并利用中序遍历的结果，来判断是左还是右还是祖先。那就是：

1.如果未到最“左”（中序遍历的当前值），那就认为是左子结点（反证法：如果是右子结点，则根比右在前，根应该早就到了最“左”）

2.如果到了最“左”，最“左”是不该有左子结点的，前序遍历中的下一个结点，要么是右子结点，要么是某个祖先的右子结点（即当前结点的兄弟或者叔叔（叔叔对应于单一条左子树下来的情况））。

后者的情况，意味着我们需要一个栈，来存储祖先，也即将前序遍历中“根-左”形式的“根”存储下来。

所谓前序，就是最“根”性，就是存储了所有可能的祖先。

所谓中序，相邻的是左根或者根右，如果是左根，根必在栈中存储过了，如果是根右，则栈中没有存储过“右”。这就是区分右子结点和祖先的右子结点的方法。

2.1 右子结点的情况：

中序的元素不出现在栈（顶），说明中序此时的形式是根右，直接添加为右子结点即可

2.2右子结点的情况：

中序的元素出现在栈顶，说明中序此时的形式是左根，而非根右，也即没有右子结点，而是有父亲，但此时遍历的结点，不一定是该父亲的右儿子，这还得根据中序来判断：如果是该父亲的右儿子，则中序的下一个结点尚未出现在栈中（因为栈是保存左子树下来的祖先的）；如果不是该父亲的右儿子，即还得往上寻找祖先，则中序的下一个结点一定在栈中。

概括说就是，当下一个结点是某个祖先的右子结点的情况时，通过一个while循坏，来寻找右子结点的祖先，寻找的依据是中序遍历。

class Solution:
    def reConstructBinaryTree(self, pre: List[int], vin: List[int]) -> TreeNode:
        n = len(pre)
        m = len(vin)
        # 每个遍历都不能为0
        if n == 0 or m == 0:
            return None
        s = []
        # 首先建立前序第一个即根节点
        root = TreeNode(pre[0])
        cur = root
        j = 0
        for i in range(1, n):
            # 要么旁边这个是它的左节点
            if cur.val != vin[j]:
                cur.left = TreeNode(pre[i])
                s.append(cur)
                # 要么旁边这个是它的右节点，或者祖先的右节点
                cur = cur.left
            else:
                j += 1
                # 弹出到符合的祖先
                while s and s[-1].val == vin[j]:
                    cur = s[-1]
                    s.pop()
                    j += 1
                # 添加右节点
                cur.right = TreeNode(pre[i])
                cur = cur.right
        return root