Question

根据先序遍历和中序遍历构造二叉树

Answer 1

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

【思路】
根据中序和先序结果 重建二叉树
1.前序结果第一个非空节点为root节点，然后在中序结果中找个根节点，则左侧为左子序列，右侧为右子序列
2.根据左子序列长度，去前序结果中找出前序左子序列和右子序列
3.递归上述步骤，直至空子序列结束
根据中序和后序结果重建二叉树与上述类似

【根据中序和先序结果重建】

【根据中序和后序结果重建】