吴良超的学习笔记

LeetCode解题报告(105. 106)--树的重构

发表于 | ， ，

本文主要从LeetCode两道题出发讲解如何从树的周游结果来重构树。这两道题分别是105. Construct Binary Tree from Preorder and Inorder Traversal和
106. Construct Binary Tree from Inorder and Postorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal要求从树的前序周游和中序周游的结果重构树。由两种周游的遍历顺序可知，两种周游方式得到的结果的结构如下

其中left_tree是root的左子树， right_tree是root的右子树。

因此通过树的根节点root以及左子树的最后一个节点，可以从两个周游结果中分别找到左子树的两种周游结果和右子树的两种周游结果。然后将问题转化为原问题的子问题，通过递归解决即可。

python实现的代码如下所示,需要注意的是下面的代码通过下标指出子树的范围，而不是通过slice，也就是preorder[i:j]的方式来将子树范围切出来，因为slice会在内存开辟新的空间，递归时会开辟大量空间而导致MLE错误：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        return self.helper(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)

    def helper(self, preorder, pleft, pright, inorder, ileft, iright):
        if pleft > pright:
            return None
        if pleft == pright:
            return TreeNode(preorder[pleft])
        inx = inorder.index(preorder[pleft])
        left_len = inx - ileft
        root = TreeNode(preorder[pleft])
        root.left = self.helper(preorder, pleft + 1, pleft + left_len, inorder, ileft, inx-1)
        root.right = self.helper(preorder, pleft + left_len + 1, pright, inorder, inx+1, right)
        return root

106. Construct Binary Tree from Inorder and Postorder Traversal的结题思路与上面一致。两种周游结果的结构如下：

同样可以通过树的根节点root以及左子树的最后一个节点，分别找到两棵子树的两种周游结果，进而将问题转化为原来问题的子问题，通过递归解决。

python实现代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        return self.helper(inorder, 0, len(inorder)-1, postorder, 0, len(postorder)-1)
        
    def helper(self, inorder, ileft, iright, postorder, pleft, pright):
        if ileft > iright: return None
        if ileft == iright: return TreeNode(inorder[ileft])
        inx = inorder.index(postorder[pright])
        left_len = inx - ileft
        root = TreeNode(postorder[pright])
        root.left = self.helper(inorder, ileft, inx-1, postorder, pleft, pleft+left_len-1) 
        root.right = self.helper(inorder, inx+1, iright, postorder, pleft+left_len, pright-1)
        return root