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