【剑指offer学习记录】7-重建二叉树

7-重建二叉树

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

题目分析

前序遍历是“中-左-右”，中序遍历是“左-中右”。

首先根据前序遍历的第一个结点即根节点，可以对中序遍历切分为左子树序列和右子树序列。

然后对前序遍历的第二个节点，又为中序遍历左子树的根结点，可以继续对左子树的根结点进行切分为左右子树。

这一过程可以看为一个递归的过程。

再看返回的过程，如果子树已经遍历完或者没有子树为叶子节点的情况，则返回上一层，此时再遍历中序遍历中的右子树。

代码实现

 1 class TreeNode:
 2      def __init__(self, x):
 3          self.val = x
 4          self.left = None
 5          self.right = None
 6  class Solution:
 7      def reConstructBinaryTree(self, preorder, inorder):
 8          if not preorder or not inorder:
 9              return None
10          root = TreeNode(preorder[0])
11          val = inorder.index(preorder[0]) #根节点位置
12          #对于前序遍历，根节点为0，则左子树前序序列为第二个值到左子树序列的长度的索引位置，
13          #而左子树序列的长度为中序序列根节点的左边的序列长度，即val,（索引序号从0开始）
14          #所以前序遍历左子树序列的范围为1-val+1
15          #同样的前序遍历右子树序列的范围为剩下的序列
16          root.left = reConstructBinaryTree(preorder[1:val+1], inorder[:val])
17          root.right = reconstructBinaryTree(preorder[val+1:], inorder[val+1:])
18          return root
19      def reConstructBinaryTree2(self, preorder, inorder):
20          if not preorder or not inorder:
21              return None
22          root = TreeNode(preorder[0])
23          val = inorder.index(preorder[0]) #根节点位置
24          left_inorder = inorder[0:val]
25          right_inorder = inorder[val+1:]
26          #下面这种写法对于序列长度计算看着更清晰
27          root.left = self.reConstructBinaryTree2(preorder[1:len(left_inorder)+1], left_inorder)
28          root.right = self.reConstructBinaryTree2(preorder[-len(right):], right_inorder)
29          #下面这种写法也可以
30          #root.left = self.reConstructBinaryTree2(preorder[1:-len(right)], left_inorder)
31          #root.right = self.reConstructBinaryTree2(preorder[len(left_inorder)+1:], right_inorder)
32          return root