通常树有如下几种遍历方式：

  • 前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。
  • 中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
  • 后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
  • 层序遍历：即广度优先遍历，先访问一级节点，后是二级节点…

最少需要两种遍历方式，才能重建二叉树。但前序和后序构建的二叉树不唯一，因为前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明
左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。总之，必须要有中序才能构建，因为没有中序，就没办法确定
树的形状。

根据前序和中序遍历重建二叉树

思路：

前序遍历序列中，第一个数字总是树的根结点的值。在中序遍历序列中，根结点的值在序列的中间，
左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。剩下的我们可以递归来实现，具体如图：

前序遍历顺序：root — preorder of left branch — preorder of right branch

中序遍历顺序：inorder of left branch — root — inorder of right branch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root
        
        pos = tin.index(pre[0])
        root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])
        root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])
        return root

根据中序遍历和后序遍历重建二叉树

思路：

在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。而在后序遍历序列中，根节点位于序列的最后。剩下的我们可以递归来实现。

中序遍历顺序：inorder of left branch — root — inorder of right branch

后序遍历顺序：postorder of left branch — postorder of right branch — root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, tin, post):
        # write code here
        if len(post) == 0:
            return None
        root = TreeNode(post[-1])
        if len(post) == 1:
            return root
        
        pos = tin.index(post[-1])
        root.left = self.reConstructBinaryTree(tin[:pos], post[:pos])
        root.right = self.reConstructBinaryTree(tin[pos+1:], post[pos:-1])
        return root

根据前序遍历和后序遍历重建二叉树

因为前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树， 如：


总之，必须要有中序才能构建，因为没有中序，你没办法确定树的形状。

思路：

前序遍历顺序：root — preorder of left branch — preorder of right branch

后序遍历顺序：postorder of left branch — postorder of right branch — root

假如说最终的二叉树可以被序列化的表述为 [1, 2, 3, 4, 5, 6, 7]，那么其前序遍历为 [1] + [2, 4, 5] + [3, 6, 7]，而后序遍历为 [4, 5, 2] + [6, 7, 3] + [1]。如果我们知道左分支有多少个结点，我们就可以对这些数组进行分组，并用递归生成树的每个分支。

算法：

我们令左分支有 L 个节点。我们知道 左分支的头节点 为 pre[1]，但它也出现在 左分支的后序表示的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性），因此 L = post.indexOf(pre[1]) + 1。

现在在我们的递归步骤中，左分支由 pre[1 : L+1] 和 post[0 : L] 重新分支，而右分支将由 pre[L+1 : N] 和 post[L : N-1] 重新分支。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
class Solution(object):
    def constructFromPrePost(self, pre, post):
        if not pre:
            return None
        root = TreeNode(pre[0])
        if len(pre) == 1:
            return root
        
        L = 1 + post.index(pre[1])
        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])
        root.right = self.constructFromPrePost(pre[L+1:], post[L:])
        return root

二叉树重建总结

一、根据前序、中序遍历重建二叉树

  1. 根据前序序列的第一个元素建立根结点
  2. 在中序序列中找到根结点位置，确定左右子树
  3. 递归由左子树的前序序列和中序序列建立左子树
  4. 递归由右子树的前序序列和中序序列建立右子树

二、根据中序、后序遍历重建二叉树

  1. 根据后序序列的最后一个元素建立根结点
  2. 在中序序列中找到根结点位置，确定左右子树
  3. 递归由左子树的后序序列和中序序列建立左子树
  4. 递归由右子树的后序序列和中序序列建立右子树

三、前序、后序遍历重建二叉树(不唯一)

  1. 根据前序序列的第一个元素建立根结点
  2. 令左分支有 L 个节点。根据前序序列，我们知道左分支的头节点 为 pre[1]，但它也出现在后序序列的左分支的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性)，因此 L = post.indexOf(pre[1]) + 1。
  3. 递归由左子树的前序序列和后序序列建立左子树
  4. 递归由右子树的前序序列和后序序列建立右子树

综上可知，二叉树的重建关键在于确定根节点和左右分支，一旦这些确定了，那么即可用递归重建此二叉树。