重建二叉树

2017-05-09 23:00 阅读 613 次 评论 1 条

重建二叉树通俗的将,就是通过前序遍历和中序遍历(或者中序遍历和后序遍历)的结果来重新构建二叉树,这道题出自剑指offer,是一个很经典的数据结构,备受面试官的青睐。下面我就为大家解析一下实现过程。

重建二叉树(前序+中序)

比如我们获取了前序遍历的序列{1,2,4,7,3,5,6,8}和中序遍历的序列{4,7,2,1,5,3,8,6}。我们要做的是首先理解前序与后序序列的特点:

①前序序列中,第一个数字总是树的根节点。

②中序序列中,找到根节点为data的数字,根节点的左边是左子树结点的值,而右子树结点的值则位于根节点的右边。

此时,我们已经找到了左、右子树的前序遍历序列和中序遍历序列,就可以用同样的方法分别构建左右子树,下面我将用递归的方法去完成二叉树的构建。

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:重建二叉树 | 术与道的分享
1024do.com导航_术与道导航平台

发表评论


表情