每日一题:leetcode106. 从中序与后序遍历序列构造二叉树

本文最后更新于:2022年8月1日 凌晨

问题描述

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

解决方案

后序遍历是左右根,因此postorder最后一个元素一定整个树的根。由于题目说明了没有重复元素,因此我们可以通过val去inorder找到根在inorder中的索引i。
而由于中序遍历是左根右,我们容易找到i左边的都是左子树,i右边都是右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
# @param inorder, a list of integers
# @param postorder, a list of integers
# @return a tree node
# 12:00
def buildTree(self, inorder, postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder.pop())
inorderIndex = inorder.index(root.val)
root.right = self.buildTree(inorder[inorderIndex + 1:], postorder)
root.left = self.buildTree(inorder[:inorderIndex], postorder)
return root

每日一题:leetcode106. 从中序与后序遍历序列构造二叉树
https://yance.wiki/106/
作者
Yance Huang
发布于
2020年5月2日
许可协议