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

image.png

0. 链接

题目链接

1. 题目

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

2. 思路1: 递归实现

• preorder从左到右的每个节点都当做根节点, 然后去inorder结果里找该元素第一次出现的位置idx
• inorder[:idx]和inorder[idx+1:]分别是preorder[0]的左子树和右子树的中序遍历结果, 则子问题转化为preorder[1:], inorder[:idx]和 preorder[1:], inorder[idx+1:]作为参数的两个子问题

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, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            root = TreeNode(preorder.pop(0))
            idx = inorder.index(root.val)
            root.left = self.buildTree(preorder, inorder[:idx])
            root.right = self.buildTree(preorder, inorder[idx + 1:])
            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()
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
print_tree(solution.buildTree(preorder, inorder))

输出结果

[3, 9, None, None, 20, 15, None, None, 7, None, None]

4. 结果

image.png