当前位置:首页 > 未命名 > 正文内容

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

u3blog8年前 (2016-04-10)未命名206

题目地址

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是其右子树 此例子比较简单,在实际操作中,还要注意步进等要素,这里说起来太抽象,这些细节会在代码中详细阐述。

代码

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

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode treeNode = build(preorder,0,preorder.length-1,inorder,0,inorder.length -1);
        return treeNode;
    }
    public TreeNode build(int[] preorder, int prel, int prer, int[] inorder, int inl, int inr){
       if(inl == inr)
           return new TreeNode(inorder[inl]);//到达叶子节点
        if(prel > prer||prel < 0||prer > preorder.length||inl > inr||inl < 0||inr > inorder.length){
            return null;
        }//根据条件判断边界以返回
        int positionI = 0,leftTreeLen;
        for(int i = inl;i <= inr;i++)
        {
           if(preorder[prel] == inorder[i])
           {
               positionI = i;
               break;
           }
        }//在中序中寻找前序节点的位置
        leftTreeLen = positionI - inl;//获取寻找到的节点的左子树节点数目以作为步进的依据
        TreeNode treeNode = new TreeNode(preorder[prel]);
        treeNode.left = build(preorder,prel+1,prel+leftTreeLen,inorder,inl,positionI - 1);//缩小范围,递归左子树
        treeNode.right = build(preorder,prel+1+leftTreeLen,prer,inorder,positionI+1,inr);//同上,递归右子树
        return treeNode;//返回节点
    }
}

总结

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

扫描二维码推送至手机访问。

版权声明:本文由u3blog发布,如需转载请注明出处。

本文链接:https://u3blog.xyz/?id=311

分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。