剑指offer面试题06----重建二叉树

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

思路：对于这个题，必须先知道二叉树的前序遍历和中序遍历的特性。前序遍历是“根左右”，中序遍历是“左根右”，因此可以通过根的位置来划分左右两边的结点。此外，在划分两边之后，对于每一边，采取的策略依然和之前一样，因此我们可以考虑采用递归来进行操作。对于边界值，当前序或者中序的长度为0时return None。

Python代码如下：

class TreeNode(object):
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None


class Solution(object):
    def reConstructBinaryTree(self, pre, tin):
        if not pre and not tin:
            return None
        root = TreeNode(pre[0])
        
        i = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
        root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
        return root


s = Solution()
pre = [1, 2, 3, 5, 6, 4]
tin = [5, 3, 6, 2, 4, 1]
res = s.reConstructBinaryTree(pre, tin)
print res.val
print res.left.val

确定left，right 中pre，tin的方法如下图所示，可以根据图形实例来进行理解

重建二叉树.jpg