LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal.jpg
LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal
Description
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
For example, given
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
描述
给定一颗二叉树的中序和后续遍历，构造原二叉树。
注意：您可以假设树中不存在重复项。
例如，给定
中序遍历 = [9,3,15,20,7]
后序遍历 = [9,15,7,20,3]
返回以下二叉树：
3
/ \
9 20
/ \
15 7
思路
- 此题目考察二叉树的构建，类型同第105题完全一致.
- 使用递归求解代码简介，但是速度较慢.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-30 11:21:05
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-30 11:21:05
# 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, inorder, postorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not inorder:
return None
return self.recursion(inorder, postorder)
def recursion(self, inorder, postorder):
#
if not inorder:
return None
elif len(inorder) == 1 and len(postorder) == 1:
root = TreeNode(inorder[0])
root.left = None
root.right = None
else:
value = postorder[-1]
root = TreeNode(value)
ino = inorder.index(value)
left = self.recursion(inorder[0:ino], postorder[0:ino])
right = self.recursion(inorder[ino+1:], postorder[ino:-1])
root.left = left
root.right = right
return root
if __name__ == "__main__":
so = Solution()
postorder , inorder = [9,15,7,20,3], [9,3,15,20,7]
res = so.buildTree(inorder, postorder)
nums, root = [], res
# 二叉树的中序遍历morris方法
while root:
if root.left:
temp = root.left
while temp.right and temp.right != root:
temp = temp.right
if not temp.right:
temp.right = root
root = root.left
if temp.right == root:
nums.append(root.val)
temp.right = None
root = root.right
else:
nums.append(root.val)
root = root.right
print(nums, inorder)
