题目

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

知识重温

二叉树遍历的方法为

# 前序遍历
def PreOrder(self, root):
    '''打印二叉树(先序)'''
    if root == None:
        return 
    print(root.val, end=' ')
    self.PreOrder(root.left)
    self.PreOrder(root.right)
# 中序遍历
def InOrder(self, root):
        '''中序打印'''
        if root == None:
            return
        self.InOrder(root.left)
        print(root.val, end=' ')
        self.InOrder(root.right)
# 后序遍历
def BacOrder(self, root):
        '''后序打印'''
        if root == None:
            return
        self.BacOrder(root.left)
        self.BacOrder(root.right)
        print(root.val, end=' ')

由上面的代码可以发现一个有趣的现象,即前中后的顺序和访问根节点的相对左右子树的位置对应,即

  • 前序遍历,第一个访问根节点
  • 中序遍历,第二个访问根节点
  • 后序遍历,第三个访问根节点

另外还有层次遍历和深度优先遍历,如下所示

# 层次优先遍历
def BFS(self, root):
    '''广度优先'''
    if root == None:
        return
    # queue队列，保存节点
    queue = []
    # res保存节点值，作为结果
    #vals = []
    queue.append(root)

    while queue:
        # 拿出队首节点
        currentNode = queue.pop(0)
        #vals.append(currentNode.val)
        print(currentNode.val, end=' ')
        if currentNode.left:
            queue.append(currentNode.left)
        if currentNode.right:
            queue.append(currentNode.right)
    #return vals

# 深度优先遍历

def DFS(self, root):
    '''深度优先'''
    if root == None:
        return
    # 栈用来保存未访问节点
    stack = []
    # vals保存节点值，作为结果
    #vals = []
    stack.append(root)

    while stack:
        # 拿出栈顶节点
        currentNode = stack.pop()
        #vals.append(currentNode.val)
        print(currentNode.val, end=' ')
        if currentNode.right:
            stack.append(currentNode.right)
        if currentNode.left:
            stack.append(currentNode.left)          
    #return vals

分析

再回来分析重建二叉树这道题,我们知道前序和中序遍历的结果,如何去重建该二叉树呢?

先找个例子试一下,如下面这颗二叉树X

    1
2        3

4 5 7 8

前序遍历结果A为: 1 2 4 5 3 7 8
中序遍历结果B为: 4 2 5 1 7 3 8

容易分析得,前序遍历的第一个元素就是树的根节点,对应2 4 5就是左子树,3 7 8 就是右子树.

如果能明确的知道前序遍历中左子树的节点和右子树的节点的分界线还是很容易的.这也是题目中强调没有重复元素的原因.

试试在中序遍历中是否可以找到答案.

不难发现,中序遍历已经把分界线给定了下来,下面就是设计算法的时候了.

利用抽象的方法,我们假设过程a能根据结果A和结果B重建出X.

过程a可划分为子过程a1,a2,a3,a4,其中

  • a1划分中序遍历中根元素r和左子树的前序遍历结果A1和右子树的遍历结果A2
  • a2划分出左子树的前序遍历结果B1和右子树的遍历结果B2
  • a3利用过程a和数据A1和B1重建左子树X1,利用过程a和数据A2和B2重建右子树X2
  • a4利用X1和X2和根元素r重建出X

过程清晰明了,感谢SICP,虽然只看了一节!

最后经过调试的通过测试的 代码如下

# -*- coding:utf-8 -*-
# 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)==1:
            T = TreeNode(pre[0])
            return T
        if len(pre)==0:
            return None
        r=pre[0]
        t=tin.index(r)
        A1=pre[1:t+1]
        A2=pre[t+1:]
        B1=tin[:t]
        B2=tin[t+1:]
        
        T1 = self.reConstructBinaryTree(A1,B1)
        T2 = self.reConstructBinaryTree(A2,B2)
        T = TreeNode(r)
        T.left = T1
        T.right =T2
        return T
赏

我很好奇