题解 | #重建二叉树#

重建二叉树

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


全部评论

相关推荐

06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务