面试题7 重建二叉树

 采用递归的方法，每次递归都可以找到子树的根结点的值。

注意点：合理确定递归函数中传递的参数。

/**
 * @Name:根据二叉树的前序遍历结果和中序遍历结果重建二叉树
 * @Description:[1,2,4,7,3,5,6,8][4,7,2,1,5,3,8,6]
 */
public class RebuildBinTree {
    public static void main(String[] args){
        int[] preOrder={1,2,4,7,3,5,6,8};
        int[] inOrder={4,7,2,1,5,3,8,6};
        ConstructBinTree constructBinTree = new ConstructBinTree();
        Node root = constructBinTree.construct(preOrder, inOrder);
        PrintBinTree printBinTree = new PrintBinTree();
        printBinTree.preOrderPrintBinTree(root);
        
        //System.out.println(root.leftNode.leftNode.rightNode.value);
        
    }
}

class Node{
    int value;
    Node leftNode=null;
    Node rightNode=null;
}

class ConstructBinTree{
    Node construct(int[] preOrder,int[] inOrder ){
        if(preOrder==null || inOrder==null || preOrder.length<=0 || inOrder.length<=0){
            return null;
        }
        return constructCore(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
    }
    
    Node constructCore(int[] preOrder,int startPreorder,int endPreorder,
            int[] inOrder,int startInoder,int endInorder){
        
        //确定根结点，每个递归函数都需要做的
        int rootValue=preOrder[startPreorder];
        Node root=new Node();
        root.value=rootValue;
        root.leftNode=root.rightNode=null;
        
        //判断递归结束条件
        if(startPreorder==endPreorder){
            if(startInoder==endInorder && preOrder[startPreorder]==inOrder[startInoder]){
                return root;
            }else{
                return null;
            }
        }
        
        //为递归准备参数
        int rootInorder=startInoder;
        while(rootInorder<=endInorder && inOrder[rootInorder]!=rootValue){
            rootInorder++;
        }
        if(rootInorder>endInorder){
            return null;
        }
        
        int leftLengh=rootInorder-startInoder;
        int leftPreorderEnd=startPreorder+leftLengh;
        
        //开始递归
        //如果存在左子树
        if(leftLengh>0){
            root.leftNode=constructCore(preOrder,startPreorder+1,leftPreorderEnd,
                    inOrder,startInoder,rootInorder-1);
        }
        //如果存在右子树
        if(leftLengh<endInorder-startInoder){
            root.rightNode=constructCore(preOrder,leftPreorderEnd+1,endPreorder,
                    inOrder,rootInorder+1,endInorder);
        }
        
        //递归结束，返回整个二叉树的根结点
        return root;
    }
}

class PrintBinTree{
    void preOrderPrintBinTree(Node root){
        if(root!=null){
            System.out.println(root.value);
            preOrderPrintBinTree(root.leftNode);
            preOrderPrintBinTree(root.rightNode);
        }
        return;
    }
}