Daily LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Medium

问题描述

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

  3
 / \
9  20
  /  \
 15   7

题目分析及代码

给定二叉树的中序和后序遍历结果，构造二叉树。

方法一

中序遍历的遍历顺序是左中右，后序遍历的遍历顺序是左右中。我们可以很容易地发现，后序遍历的最后一个元素就是二叉树的根元素，根据这个根元素以及中序遍历的结果，我们就能够获得左右子树的遍历结果；此时，子问题变成了根据左右子树的中序、后序遍历结果构造二叉树，我们通过递归即可解决这个问题。

代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def restoreTree(inorder, in_start, in_end, postorder, post_start, post_end):
            if in_start > in_end or post_start > post_end:
                return None
            
            treeNode = TreeNode(postorder[post_end])
            
            for i in range(in_end + 1):
                if inorder[i] == postorder[post_end]:
                    treeNode.left = restoreTree(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1)
                    treeNode.right = restoreTree(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1)

            return treeNode

        tree = restoreTree(inorder, 0, len(inorder) - 1, postorder, 0, len(postorder) - 1)

        return tree

LeetCode论坛看到的方法2

没有右子树的二叉树中序和后序遍历结果相同：

      1
     /
    2
中序：1，2
后序：1，2

但是，没有左子树的二叉树中序和后序遍历结果是不同的：

      1
       \
    	  2
中序：1，2
后序：2，1

上面我们已经提到过，后序遍历的最后一个元素就是当前树的根节点，因此，我们可以从右向左、根据遍历结果构造左右子树。

如果中序和后序的值相同，那么当前值一定是左子树，否则就是右子树，我们将建立的新节点都存储在栈中，当作当前大小为1的子树的根节点，这样，在遍历完成后根据栈建立二叉树。

代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
  	def buildTree(self, inorder, postorder):
      	if len(inorder) == 0: return None
    		root = TreeNode(postorder[-1])
        stack = [root]
        in_index = len(inorder) - 1
        # 根节点已经保存到栈中，因此，后序遍历的最后一个元素无需处理
        post_index = len(postorder) - 2    
        # 比较中序最右元素和栈顶元素
        while True:
            # 栈顶元素与中序遍历的最右元素相等
            # 第一次出现这种情况时，意味着我们遍历到了中序序列中的根节点
            # 这意味着我们已经建立完了右子树，并且这些节点已经保存在了栈中
            # 我们无视这些节点即可，右子树建立过程在'else'中
          	if stack[-1].val == inorder[in_index]:
            		n = stack.pop()
                in_index -= 1
                if in_index == -1:
                  	break
                # 越过中序遍历序列中的所有右子树节点
                if stack and inorder[in_index] == stack[-1].val:
                  	continue                
                
                # 建立左子树
                # n是从栈中取出的当前节点
                n.left = TreeNode(postorder[post_index])
                post_index -= 1
                stack.append(n.left)
                
            # 栈顶元素与中序最右元素不同时，我们需要建立右子树
            else:
              	n = TreeNode(postorder[post_index])
	              post_index -= 1
                stack[-1].right = n
                stack.append(n)
                
        return root