题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
NC12 重建二叉树
中等
知识点:树,dfs,数组 描述 给定节点数为 n 二叉树的前序遍历和中序遍历结果,请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建出如下图所示。
提示: 1.vin.length == pre.length 2.pre 和 vin 均无重复元素 3.vin出现的元素均出现在 pre里 4.只需要返回根结点,系统会自动输出整颗树做答案对比 数据范围:n \le 2000n≤2000,节点的值 -10000 \le val \le 10000−10000≤val≤10000 要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n) 示例1 输入: [1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6] 复制 返回值: {1,2,3,4,#,5,6,#,7,#,#,8} 复制 说明: 返回根节点,系统会输出整颗二叉树对比结果,重建结果如题面图示
思路
- 首先明确前序遍历与中序遍历的特点,前序遍历是根左右,中序遍历是左根右。
- 因此前序遍历数组中第一个结点一定是根节点,将这个根节点放在中序遍历中,该结点左边是左子树,结点右边是右子树。
- 然后根据中序遍历左子树长度对应分割出前序遍历的左右子树后,再继续递归对左右子树继续重复步骤1,2,3,递归的边界条件就是左右子树为空或者是叶子结点。
解题过程
如图:
时间和空间复杂度如下
该题涉及的是前中序重建二叉树,如果是中后序重建二叉树,原理一样,只不过后序遍历是取每个数组最后一个。
觉得本篇文章有用的不妨点个赞,谢谢