问题描述

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。

注意:

  • 二叉树中每个节点的值都互不相同;
  • 输入的前序遍历和中序遍历一定合法;

样例

给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]

返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
    3
   / \
  9  20
    /  \
   15   7

解决方案

思路:前序的第一个元素是根结点的值,在中序中找到该值,中序中该值的左边的元素是根结点的左子树,右边是右子树,然后递归的处理左边和右边

不太理解的话需要配合示意图来看:

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/

class Solution(object):
    def buildTree(self, preorder, inorder):
        if not preorder or not inorder:
            return None

        index = inorder.index(preorder[0])  # 找到前序遍历结果中第一位对应在中序遍历结果中的位置
        left = inorder[0:index]
        right = inorder[index+1:]
        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1:1+len(left)], left)
        root.right = self.buildTree(preorder[-len(right):], right)
        return root

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

八月杂记 上一篇
剪绳子 下一篇