leetcode-106

106. 从中序与后序遍历序列构造二叉树

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

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

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

官方解法

递归

后序遍历的数组最后一个元素代表的即为根节点。

知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

注意这里有需要先创建右子树，再创建左子树的依赖关系。可以理解为在后序遍历的数组中整个数组是先存储左子树的节点，再存储右子树的节点，最后存储根节点，如果按每次选择「后序遍历的最后一个节点」为根节点，则先被构造出来的应该为右子树。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def myBuildTree(in_left,in_right):
            # 如果这里没有节点构造二叉树了，就结束
            if in_left > in_right:
                return None
            
            # 选择 post_idx 位置的元素作为当前子树根节点
            val = postorder.pop()
            root = TreeNode(val)

            # 根据 root 所在位置分成左右两棵子树，定位后序节点在中序中的位置
            index = idx_map[val]

            # 构造右子树
            root.right = myBuildTree(index + 1, in_right)

            # 构造左子树
            root.left = myBuildTree(in_left, index - 1)

            return root
        # 建立（元素，下标）键值对的哈希表
        idx_map = {val:idx for idx, val in enumerate(inorder)} 
        return myBuildTree(0, len(inorder) - 1)

迭代

迭代法是一种非常巧妙的实现方法。迭代法的实现基于以下两点发现。

• 如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子。
• 如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子。

「反向」的意思是交换遍历左孩子和右孩子的顺序，即反向的遍历中，右孩子在左孩子之前被遍历。

因此可以使用和「105. 从前序与中序遍历序列构造二叉树」的迭代方法类似的方法构造二叉树。

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

• u 是 $v$ 的右儿子。这是因为在遍历到 $u$ 之后，下一个遍历的节点就是 $u$的双亲节点，即 $v$；

• $v$没有右儿子，并且$u$是$v$的某个祖先节点（或者$v$本身）的左儿子。

  如果$v$没有右儿子，那么上一个遍历的节点就是$v$的左儿子。

  如果$v$没有左儿子，则从$v$开始向上遍历$v$的祖先节点，直到遇到一个有左儿子（且$v$不在它的左儿子的子树中）的节点$v_a$，那么$u$就是$v_a$的左儿子。

算法

• 我们用一个栈和一个指针辅助进行二叉树的构造。初始时栈中存放了根节点（后序遍历的最后一个节点），指针指向中序遍历的最后一个节点；

• 我们依次枚举后序遍历中除了第一个节点以外的每个节点。

  如果 index 恰好指向栈顶节点，那么我们不断地弹出栈顶节点并向左移动 index，并将当前节点作为最后一个弹出的节点的左儿子；

  如果 index 和栈顶节点不同，我们将当前节点作为栈顶节点的右儿子；

• 无论是哪一种情况，我们最后都将当前的节点入栈。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if len(postorder) == 0:
            return None
        
        root = TreeNode(postorder[-1])

        stack = list()
        stack.append(root)

        inordIndex = len(inorder) -1

        for i in range(len(postorder)-2,-1,-1):
            postOrderVal = postorder[i]

            node = stack[-1]

            if node.val != inorder[inordIndex]:
                node.right = TreeNode(postOrderVal)
                stack.append(node.right)
            else:
                while stack and stack[-1].val == inorder[inordIndex]:
                    node = stack.pop()
                    inordIndex -= 1
                
                node.left = TreeNode(postOrderVal)
                stack.append(node.left)
        
        return root