Leetcode 889.根据前序和后序遍历构造二叉树

Posted on |

889.根据前序和后序遍历构造二叉树

题目

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

1
2
3
4
示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

提示
1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, …, pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

方法

前序遍历为：
(root node) (preorder of left branch) (preorder of right branch)

而后序遍历为：
(postorder of left branch) (postorder of right branch) (root node)

方法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        length = len(pre)
        if length==0:
            return None
        root = TreeNode(pre[0])
        if length == 1:
            return root
        i = post.index(pre[1])
        root.left = self.constructFromPrePost(pre[1:1+i+1],post[:i+1])
        root.right = self.constructFromPrePost(pre[1+i+1:],post[i+1:-1])
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        if not pre:
            return None
        node = TreeNode(pre[0])
        i = 1
        while(i<len(pre) and pre[i]!=post[-2]):
            i+=1
        node.left = self.constructFromPrePost(pre[1:i],post[:i-1])
        node.right = self.constructFromPrePost(pre[i:],post[i-1:-1])
        return node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def constructFromPrePost(self, pre, post):
        def make(i0, i1, N):
            if N == 0: return None
            root = TreeNode(pre[i0])
            if N == 1: return root

            for L in xrange(N):
                if post[i1 + L - 1] == pre[i0 + 1]:
                    break

            root.left = make(i0 + 1, i1, L)
            root.right = make(i0 + L + 1, i1 + L, N - 1 - L)
            return root

        return make(0, 0, len(pre))

方法2：迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        stack = [TreeNode(pre[0])]
        j = 0
        for v in pre[1:]:
            node = TreeNode(v)
            while stack[-1].val == post[j]:
                stack.pop()
                j += 1
            if not stack[-1].left:
                stack[-1].left = node
            else:
                stack[-1].right = node
            stack.append(node)
        return stack[0]