【解题报告】 前序遍历和中序遍历树构造二叉树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是其右子树 此例子比较简单，在实际操作中，还要注意步进等要素，这里说起来太抽象，这些细节会在代码中详细阐述。

代码

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

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;//返回节点
    }
}

总结

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