根据先序遍历和后序遍历构建二叉树

关于先序遍历、中序遍历、后序遍历的定义能够参考这篇博客二叉树的遍历规则。html

目前可以百度到的问题大多都是根据（先序&中序）或（中序&后序）序列构建惟一二叉树，其中贴出一些提供思路的博客：二叉树的前序中序后序遍历相互求法node

可是这篇博客并无给出**（前序&后序）**的求解方法。事实上，根据前序和后序构建的二叉树不惟一，理由是前序与后序都没有明确规定节点间的父子关系，例以下图所示：

下面给出已知前序&后序序列，求任一解的方法。该题同时出现于LeetCode Weekly Contest 98python

LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversalweb

Return any binary tree that matches the given preorder and postorder
traversals. Values in the traversals pre and post are distinct
positive integers.svg

Example 1: Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]函数

该题给出的解以下图所示：
post

解题思路：
仍是能够根据通常的思路，采用递归思想，对于每个先序序列，划分出对应的根节点、左子树、右子树范围便可自上而下构建出二叉树。
例如对于上例中的先序序列[1,2,4,5,3,6,7]，第一个节点必定为根节点，第2到第i个节点为左子树，第i+1到最后一个节点为右子树，那么问题就能够简化为：如何肯定左右子树分界点？
3d

对于这个简化事后的问题，从后序遍历序列上很容易获得答案：
code

所以，能够写出递归函数的核心代码：xml

#伪代码，用于理解思路
def func(pre, post):   #pre为先序序列，post为后序序列
    ...
    node = Node(pre[0])
    index = find_index(post, pre[1].val)  #查找分割点下标
    node.left = func(pre[1:index+2], post[:i+1])
    node.right = func(pre[index+2:], post[i+1:-1])
    return node

对于该题的完整解法以下所示（python）：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructFromPrePost(self, pre, post):
        """
        :type pre: List[int]
        :type post: List[int]
        :rtype: TreeNode
        """
        def fun(p, t):
            if len(p) == 0:
                return None
            node = TreeNode(p[0])
            if len(p) == 1:
                return node
            i = 0
            while p[1] != t[i]:
                i += 1
            node.left = fun(p[1:i+2], t[:i+1])
            node.right = fun(p[i+2:], t[i+1:-1])
            return node
        return fun(pre, post)

拓展问题：如何输出全部知足要求的二叉树？ 以上。