算法题--根据中序和后序遍历的结果复原一棵二叉树

2020-04-29 本文已影响0人岁月如歌2020

0. 链接

1. 题目

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:

2. 思路1: 递归实现

首先找到根节点, 即postorder[-1]
然后找到根节点元素在inorder中的位置idx
可以很容易推理出, inorder[:idx]即为左子树的inorder结果, 相应的postorder[:idx]也为左子树的postorder结果;
从而inorder[idx + 1:]和postorder[idx:]为右子树的inorder和postorder结果
根据上述推理, 继续递归调用
root.left = 构建左子树(inorder[:idx], postorder[:idx])
root.right = 构建右子树(inorder[idx + 1:], postorder[idx:])

3. 代码

# coding:utf8
from typing import List


# 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:
        if inorder:
            root = TreeNode(postorder.pop())
            idx = inorder.index(root.val)
            root.left = self.buildTree(inorder[:idx], postorder[:idx])
            root.right = self.buildTree(inorder[idx + 1:], postorder[idx:])
            return root
        else:
            return None


def print_tree(root):

    def traversal(root, results):
        if root is None:
            results.append(None)
            return

        results.append(root.val)
        if root.left is not None:
            traversal(root.left, results)
        else:
            results.append(None)
        if root.right is not None:
            traversal(root.right, results)
        else:
            results.append(None)

    results = list()
    traversal(root, results)
    print(results)


solution = Solution()
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
print_tree(solution.buildTree(inorder, postorder))

inorder = [1, 2, 3, 4]
postorder = [2, 1, 4, 3]
print_tree(solution.buildTree(inorder, postorder))

输出结果

[3, 9, None, None, 20, 15, None, None, 7, None, None]
[3, 1, None, 2, None, None, 4, None, None]

4. 结果

image.png

5. 思路2: 递归时不使用切片

6. 代码

class Solution1:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        value_to_idx = dict()
        for idx, value in enumerate(inorder):
            value_to_idx[value] = idx

        def build(inorder, postorder, in_start, in_end, post_start, post_end):
            if in_start <= in_end:
                root = TreeNode(postorder[post_end])
                in_idx = value_to_idx[root.val]
                in_idx_delta = in_idx - in_start
                root.left = build(inorder, postorder,
                                  in_start, in_idx - 1,
                                  post_start, post_start + in_idx_delta - 1)
                root.right = build(inorder, postorder,
                                   in_start + in_idx_delta + 1, in_end,
                                   post_start + in_idx_delta, post_end - 1)
                return root
            else:
                return None

        return build(inorder, postorder, 0, len(inorder) - 1, 0, len(postorder) - 1)


def print_tree(root):

    def traversal(root, results):
        if root is None:
            results.append(None)
            return

        results.append(root.val)
        if root.left is not None:
            traversal(root.left, results)
        else:
            results.append(None)
        if root.right is not None:
            traversal(root.right, results)
        else:
            results.append(None)

    results = list()
    traversal(root, results)
    print(results)


solution = Solution1()
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
print_tree(solution.buildTree(inorder, postorder))

inorder = [1, 2, 3, 4]
postorder = [2, 1, 4, 3]
print_tree(solution.buildTree(inorder, postorder))