题解 | #重建二叉树#
重建二叉树
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