重建二叉树
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2018/7/29 19:39
# @File : # 007.py
# @Software: PyCharm
# @Author : wxw
# @Contact : weixianwei0129@163.com
# @Desc : 重建二叉树
"""
preOrder{1,2,4,7,3,5,6,8}和midOrder{4,7,2,1,5,3,8,6}
"""
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def Construct(pre, tin):
if len(pre) == 0:
return None
if len(pre) == 1:
return TreeNode(pre[0])
root = TreeNode(pre[0])
idx = tin.index(pre[0])
root.left = Construct(pre[1:idx+1], tin[:idx])
root.right = Construct(pre[idx+1:], tin[idx+1:])
return root
先序遍历: 第一个节点为根节点;
中序遍历: 根节点在中间位置,两边分别为左子树和右子树.
