leetcode-105

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

官方题解

递归

二叉树前序遍历的顺序为：

• 先遍历根节点；

• 随后递归地遍历左子树；

• 最后递归地遍历右子树。

二叉树中序遍历的顺序为：

• 先递归地遍历左子树；

• 随后遍历根节点；

• 最后递归地遍历右子树。

在「递归」地遍历某个子树的过程中，我们也是将这颗子树看成一颗全新的树，按照上述的顺序进行遍历。挖掘「前序遍历」和「中序遍历」的性质，我们就可以得出本题的做法。

对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。

由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，

我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(pre_left,pre_right, in_left,in_right):
            if pre_left > pre_right:
                return None

            preorder_root = pre_left # 先序遍历第一个节点为根节点
            inorder_root = index[preorder[preorder_root]] # 定位中序遍历中的跟节点

            # 建立根节点
            root = TreeNode(preorder[preorder_root])

            size_left_subtree = inorder_root - in_left # 得到左子树的数目

            # 递归构造左子树，并连接到根节点
            # 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素
            # 就对应了
            # 中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(pre_left+1,pre_left+size_left_subtree,in_left,inorder_root-1)

            # 递归地构造右子树，并连接到根节点
            # 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素
            # 就对应了
            # 中序遍历中「从 根节点定位+1 到 右边界」的元素
            root.right = myBuildTree(pre_left + size_left_subtree + 1, pre_right, inorder_root + 1, in_right)
            return root
        n = len(preorder)
        # 构造哈希映射，帮助我们快速定位根节点
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0, n - 1, 0, n - 1)

迭代

对于前序遍历中的任意两个连续节点 $u$和$v$，根据前序遍历的流程，我们可以知道$u$ ,$v$只有两种可能的关系：

• v 是 u的左儿子。这是因为在遍历到 u之后，下一个遍历的节点就是 u 的左儿子，即 v；
• u 没有左儿子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右儿子。如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。如果 没有右儿子，我们就会向上回溯，直到遇到第一个有右儿子（且 $u$ 不在它的右儿子的子树中）的节点 $u_a$，那么 $v$ 就是 $u_a$的右儿子。

算法

• 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（前序遍历的第一个节点），指针指向中序遍历的第一个节点；
• 我们依次枚举前序遍历中除了第一个节点以外的每个节点。如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向右移动 index，并将当前节点作为最后一个弹出的节点的右儿子；如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的左儿子；
• 无论是哪一种情况，我们最后都将当前的节点入栈。

最后得到的二叉树即为答案。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
           return None
        
        root = TreeNode(preorder[0])
        stack = [root]
        inorderIndex = 0

        for i in range(1,len(preorder)):
            preorderVal = preorder[i]
            node = stack[-1] # 取当前节点的父节点

            # 先序与中序比较，第一种可能，是左儿子
            if node.val != inorder[inorderIndex]: 
                node.left = TreeNode(preorderVal)
                stack.append(node.left)
            else:
                # 弹出stack中与当值相同的元素，用于回溯，既找到父节点
        
                while stack and stack[-1].val == inorder[inorderIndex]: 
                    node = stack.pop()
                    # print("==>",node.val)
                    inorderIndex += 1

                node.right = TreeNode(preorderVal)
                stack.append(node.right)
        return root