已知一二叉树先序遍历和中序遍历顺序，如何求其后续遍历？

[spencerqiu]

如：
先：1 2 4 3 5 7 6
中：4 2 1 5 7 3 6

我的想法似乎只有慢慢用人脑回溯，然后画出一颗二叉树，可能我真的比较笨……

感觉怪怪的，先续遍历至少能看出根节点是 1 ，左子树是 2 （？），于是中序遍历能否也可以看出左子树是 4 呢，真是凌乱了……

[dingyaguang117]

建树再后序呗，代码目测二三十行

[Monad]

考虑输入Array MakePostOrder(Array pre_order, Array in_order)
先取in_order[0]，在pre_order中找到对应的位置pos，那么从0-(pos-1)就是左子树，(pos+1)到pre_order.size()就是右子树（边界情况就自己考虑了）,于是return MakePostOrder(left, right) ++ [in_order[0]]
这样不断递归就行

[Monad]

修正：right不是right, 是0-(pos-1)在in_order中的那一部分
于是编程MakePostOrder(left, left2) + MakePost(right, right2) ++ [in_order[0]]

[spencerqiu]

@dingyaguang117
@Monad
怪我没说清楚，这是笔试题。

[kokdemo]

中序和先序就已经可以把树写出来了……

[lzt163]

大概说一下
就是每次用先序的第一个去中序找
找到好把中序分为两段
再用先序中的下一个
在中序分开来的几段中找
再把这段分开来的中序再分为两段
。
。
。
一直分到找到所有位置

[Mutoo]

先：1 2 4 3 5 7 6
中：4 2 1 5 7 3 6

构造树：从先序开始，第一个是1，于是在中序的队列中，1左边的都在左子树，右边的都在右子树。以此类推，就把整个树画出来了。然后得到后序。

[viowan]

楼上说对了，根据中序和先序推出树来。之前数据结构考过类似的题目！
想了下：
4
2 5
1 7
3 6
大概树的结构是上面这样子的！
所以后序遍历应该是：1、2、3、6、7、5、4
我记得之前好像有个定理就是中序遍历第一个一定是根节点，先序遍历也有一个是什么，忘记了~

[hooluupog]

这个不需要建树，先序和中序已经将2叉树线性化了。只需要通过中序和先序间的关系来推导出后序就行了。用递归或者栈都行。
大概的思路：
1）先序序列第一个元素为根结点，将线性表分为两部分（即二叉树的左右子树），再用中序去分别处理两个部分(即判断左右)。
2）对每个部分再执行1），直到剩余一个结点，按照LRN的顺序输出。
上面是个递归的过程，最终会得到一个后序序列。

[xiaoai]

中序就是一棵树的竖直投影...所以这题就很好解了

[youyongsong]

我在OJ上刷过这道题，解题思路和代码都贴到Gist上了，有兴趣可以看一下。
https://gist.github.com/8420954a0f1c35b59df4.git

[hooluupog]

刚刚写了一个，只随便验证了几个数据点，对错不敢保证。
/*
* input preOrder and inOrder list of a binary tree,
* output its postOrder list.
*/

package main

import "fmt"

var illegal bool

func PostOrder(preOrder, inOrder string) string {
if len(preOrder) == 0 || len(inOrder) == 0 {
return ""
}
root := preOrder[0]
i := 0
for i < len(inOrder) && inOrder[i] != root {
i++
}
if i == len(inOrder) {
illegal = true
return ""
}
return PostOrder(preOrder[1:i+1], inOrder[0:i]) +
PostOrder(preOrder[i+1:len(preOrder)], inOrder[i+1:len(inOrder)]) + string(root)

}
func main() {
var preOrder, inOrder string
fmt.Scan(&preOrder, &inOrder)
illegal = false
res := PostOrder(preOrder, inOrder)
if illegal {
fmt.Println("illegal input")
} else {
fmt.Println(res)
}
}

[mulog]

递归
面试被问过 没写出来 后来自己回去写了一个－—－
https://gist.github.com/mulog1990/ece03417a494911038bf

[jedihy]

leetcode上刷过