根据先序遍历和后序遍历构建⼆叉树
关于先序遍历、中序遍历、后序遍历的定义可以参考这篇博客。
⽬前能够百度到的问题⼤多都是根据（先序&中序）或（中序&后序）序列构建唯⼀⼆叉树，其中贴出⼀些提供思路的博客：
但是这篇博客并没有给出**（前序&后序）**的求解⽅法。事实上，根据前序和后序构建的⼆叉树不唯⼀，理由是前序与后序都没有明确规定节点间的⽗⼦关系，例如下图所⽰：
下⾯给出已知前序&后序序列，求任⼀解的⽅法。该题同时出现于LeetCode Weekly Contest 98
LeetCode 889. Construct Binary Tree from Preorder and Postorder Traversal
Return any binary tree that matches the given preorder and postorder
traversals. Values in the traversals pre and post are distinct
positive integers.
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]
该题给出的解如下图所⽰：
解题思路：
还是可以根据⼀般的思路，采⽤递归思想，对于每⼀个先序序列，划分出对应的根节点、左⼦树、右⼦树范围即可⾃上⽽下构建出⼆叉树。例如对于上例中的先序序列[1,2,4,5,3,6,7]，第⼀个节点⼀定为根节点，第2到第i个节点为左⼦树，第i+1到最后⼀个节点为右⼦树，那么问题就可以简化为：如何确定左右⼦树分界点？
对于这个简化过后的问题，从后序遍历序列上很容易得到答案：
因此，可以写出递归函数的核⼼代码：
#伪代码，⽤于理解思路
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)
拓展问题：如何输出所有满⾜要求的⼆叉树？以上。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。