已知先序遍历和中序遍历及已知中序遍历和后序遍历重建二叉树的Python递归和迭代解法
105. Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution
# 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
"""
if inorder:
index = inorder.index(preorder.pop(0))
root = TreeNode(inorder[index])
root.left = self.buildTree(preorder, inorder[:index])
root.right = self.buildTree(preorder, inorder[index+1:])
return root
Iteration version
class Solution(object):
def buildTree(self, preorder, inorder):
if len(preorder) == 0:
return None
head = TreeNode(preorder[0])
stack = [head]
i = 1
j = 0
while i < len(preorder):
temp = None
t = TreeNode(preorder[i])
while stack and stack[-1].val == inorder[j]:
temp = stack.pop()
j += 1
if temp:
temp.right = t
else:
stack[-1].left = t
stack.append(t)
i += 1
return head
106. Construct Binary Tree from Inorder and Postorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
Solution
# 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, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if inorder:
temp = postorder[-1]
postorder.remove(temp) # duplicates do not exist in the tree
index = inorder.index(temp)
root = TreeNode(temp)
root.right = self.buildTree(inorder[index+1:],postorder) # 先重建右子树
root.left = self.buildTree(inorder[:index],postorder)
return root
Iteration version
# 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, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
oi, pi = 0,0
stack = []
cur = None
while pi < len(postorder):
if len(stack) and stack[-1].val == postorder[pi]:
stack[-1].right = cur
cur = stack.pop()
pi += 1
else:
stack.append(TreeNode(inorder[oi]))
stack[-1].left = cur
cur = None
oi += 1
return cur