【解题报告】 前序遍历和中序遍历树构造二叉树Construct Binary Tree from Preorder and Inorder Traversal

题目地址

http://www.lintcode.com/zh-cn/problem/construct-binary-tree-from-preorder-and-inorder-traversal/

题目大意

给出一棵二叉树的前序和中序遍历,恢复二叉树的树结构

思路

基于前序和中序遍历的思路,我们可以找到规律
在前序中找到一个点,并在中序中找到此点的位置,在此点左边就是该节点的左子树,右边就是右子树
那么我们可以不断的重复这个过程,直到达到叶子节点,即没有左右子树的情况,以此类推,就可以恢复树结构
一个例子:
前序
2,1,3
中序
1,2,3
在前序中找到第一个节点,2,在中序中找到2,那么1是其左子树,3是其右子树

此例子比较简单,在实际操作中,还要注意步进等要素,这里说起来太抽象,这些细节会在代码中详细阐述。

代码

有了思路,我们就可以开始写代码了
代码如下

总结

对于此类题目,很容易从数据上找到规律,但是代码实现的时候因为没有考虑递归的方法,造成了很大的麻烦
使用了递归之后,我们只需要把注意力击中到某一次的过程就行了,此题就可以作为一个很好的例子,自己写一次之后对于递归的思想理解有很大的帮助。

u3coding
A software developer

Leave a Comment

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.