重建二叉树

题目描述:

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

    3

  / \

  9  20

    /  \

  15  7


解法:

递归

前序遍历:左-根-右 可得 前序遍历数组的第一个元素即为根元素

在中序遍历数组中找到根元素的位置 从该位置分为左右两个数组 分别为左子树和右子树

然后在左子树和右子树 继续递归构造树


©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容