重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解答

前序打印先打父节点，再打左节点、最后打右节点，所有第一个元素肯定是根节点。

中序打印，先打左节点，再打父节点，最后打右节点，所有根据前序打印确定的根节点可以判断，左分支的所有元素和又分支的所有元素，就剩下递归了。

# 创建节点
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:

    def reConstructBinaryTree(self, pre, tin):
        if len(pre) == 1:
            head = TreeNode(pre[0])
            return head
　　　　 # 定义二叉树
        head = TreeNode(pre[0])
        ind = tin.index(pre[0])
        if ind > 0:
            head.left = self.reConstructBinaryTree(pre[1:ind+1], tin[:ind])
        if ind < len(tin) - 1:
            head.right = self.reConstructBinaryTree(pre[ind+1:], tin[ind+1:])
        return head
# 注意python的set是无序的，所有用[]替代{}
ret = Solution().reConstructBinaryTree([1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6])


# 验证前序打印
def preOrder(head):
    if head:
        print head.val
        preOrder(head.left)
        preOrder(head.right)
 
preOrder(ret)

# 验证中序打印
def tinOrder(head):
    if head:
        tinOrder(head.left)
        print head.val
        tinOrder(head.right)

tinOrder(ret)

结束