Leetcode 105.从前序与中序遍历序列构造二叉树
题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
解题思路
根据前序遍历,可以确定根节点。根据中序遍历,可以找到此根节点下左子树与右子树的节点。
则可采用递归的方式进行构建:
- 判断当前前序遍历序列中元素个数
- 若个数大于1,则建立根节点,在中序遍历序列中确定左子树节点数目和右子树节点数目
- 随后,对左右子树递归进行建立。将前序遍历序列与中序遍历序列进行切片,传入函数中
- 若个数为1,则只进行根节点的建立
- 若个数为0,返回None
- 最后返回建立的根节点
代码
# 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 buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
def build(pre,ino):
if len(pre)>1:
r=TreeNode(pre[0])
index=ino.index(pre[0])
left_num=index
right_num=len(ino)-1-index
r.left=build(pre[1:1+left_num],ino[0:index])
r.right=build(pre[1+left_num:],ino[index+1:])
elif len(pre)==1:
r=TreeNode(pre[0])
else:
return None
return r
return build(preorder,inorder)
结果
反思
目前执行速度最快的代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not inorder or not preorder:
return
root = TreeNode(preorder[0])
stack = [root]
i = 0
for node in preorder[1:]:
parent = stack[-1]
if parent.val != inorder[i]:
parent.left = TreeNode(node)
stack.append(parent.left)
else:
while stack and stack[-1].val == inorder[i]:
parent = stack.pop()
i += 1
parent.right = TreeNode(node)
stack.append(parent.right)
return root
这是一种非递归的建立方式。