类型
- 已知先序与中序遍历，求后序遍历
- 已知中序与后序遍历，求先序遍历
- 但是已知先序与后序遍历，不可求得中序
- 也就是必须知道中序！
思路类似，都是先求原始二叉树，再求第三者
1.已知先中，求后序
栗子1：
先序：ABCDEFGH
中序：BDCEAFHG
解题
1.因为先序是先访问根节点，所以A为根节点；
2.因为中序是在树的两边中间访问根节点，并且按大致从左往右的顺序，
所以，BDCE分布在根节点A的左子树，FHG分布在根节点A的右子树；
3.BDCE在先序中是先访问B的，所以B是A的左子树部分的根节点；
因为中序访问时根节点B大致在中间，所以DCE就属于B的右子树部分；
4.同理，C是DCE部分的根节点；D是C的左子树部分，E是C的右子树部分；
5.同样的，也可以判断出A的右子树部分FHG的情况。
答案
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307431281.png "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307431281.png!water.jpg "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
栗子2：
先序：ABDGHCEFI
中序：GDHBAECIF
答案
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307492447.png "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307492447.png!water.jpg "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
2.已知中后，求先序
提示：
后序遍历是最后访问根节点的
后序遍历是最后访问根节点的
栗子
中序：BDCEAFHG
后序：DECBHGFA
答案
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307541669.png "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
![[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081307541669.png!water.jpg "[笔记]已知二叉树的两种遍历顺序求第三种遍历顺序")
![[笔记]Java多线程学习之wait,notify,notifyAll](https://cdn.jysafe.cn/wp-content/uploads/2020/06/2020062811311744.png!githumb3.jpg)
![[笔记]特殊控制语句](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019082802401044.jpg!githumb3.jpg)
![[笔记]二叉树的三种遍历方式](https://cdn.jysafe.cn/wp-content/uploads/2019/08/2019081301372643-e1565660364980.png!githumb3.jpg)
![[知乎]如何理解汉诺塔的递归？](https://cdn.jysafe.cn/assets/images/pics/3.png!githumb3.jpg)
