重建二叉树

读书笔记

出自《剑指Offer》的面试题6，原题题目为：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输出的前序遍历和中序遍历的结果中都不含重复的数字。
显然，要完成这道题，必须搞清楚一个二叉树的前序遍历，中序遍历之间有什么关系，我们可以通过一个实际的例子来研究。

            3

       /          \

     8             6 

  /      \        /     \

 2       4       7       5

 \                      /  \

     9                 1    0

（由于作业部落暂时不支持上传图片，用外链又一时不知道该先上传到哪去，只能随意画一画了）那么此二叉树对于的前序遍历为：[3-8-2-9-4-6-7-5-1-0]，中序遍历为[2-9-8-4-3-76--1-5-0]。我们可以很明显的看到前序遍历的第一个值必然是二叉树的根节点值，那么就可以确定中序遍历中被根节点分隔的正好就是左子树和右子树，然后对于各个左子树和右子树，又可以通过前序遍历的第一个值在中序遍历序列中划分左右子树，这就像一个递归一样。
但是有了这个思路不代表代码能写出来，具体在对数中的节点进行操作的时候，还是很生疏的。我再尝试了一段时间以后，还是没能完整得写出这个题的程序，还是把网上的例子贴过来参考一下吧。
例1：

class Node {
    Node left = null;
    Node right = null;
    char value;
}
public class BinaryTreeBuilder {
    /**
     * 根据前序遍历和中序遍历重建二叉树子树
     * @param preOrder 前序遍历数组
     * @param start 子树起始位置
     * @param inOrder 中序遍历数组
     * @param end 中序遍历结束位置
     * @param length 子树节点树
     * @return 子树的根节点
     */
    public static Node buildTree(char[] preOrder, int start,
            char[] inOrder, int end, int length) {
        //参数验证
        if (preOrder == null || preOrder.length == 0 || inOrder == null
                || inOrder.length == 0 || length <= 0) {
            return null;
        }
        //建立子树根节点
        char value = preOrder[start];
        Node root = new Node();
        root.value = value;
        //递归终止条件：子树只有一个节点
        if (length == 1)
            return root;
        //分拆子树的左子树和右子树
        int i = 0;
        while (i < length) {
            if (value == inOrder[end - i]) {
                break;
            }
            i++;
        }
        //建立子树的左子树
        root.left = buildTree(preOrder, start + 1, inOrder, end - i - 1, length - 1 - i);
        //建立子树的右子树
        root.right = buildTree(preOrder, start + length - i, inOrder, end, i );
        return root;
    }
    public static void main(String[] args) {
        char[] preOrder = new char[] {'a', 'b', 'd', 'c', 'e', 'f'};
        char[] inOrder = new char[] {'d', 'b', 'a', 'e', 'c', 'f'};
        Node root = buildTree(preOrder, 0, inOrder, inOrder.length - 1, inOrder.length);
    }
}

例2：

public class BuildTreePreOrderInOrder {
    /**
     * Build Binary Tree from PreOrder and InOrder
     *  _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11
     */
    public static void main(String[] args) {
        BuildTreePreOrderInOrder build=new BuildTreePreOrderInOrder();
        int[] preOrder = {7,10,4,3,1,2,8,11};
        int[] inOrder = {4,10,3,1,7,11,8,2};
        Node root=build.buildTreePreOrderInOrder(preOrder,0,preOrder.length-1,inOrder,0,preOrder.length-1);
        build.preOrder(root);
        System.out.println();
        build.inOrder(root);
    }
    public Node buildTreePreOrderInOrder(int[] preOrder,int begin1,int end1,int[] inOrder,int begin2,int end2){
        if(begin1>end1||begin2>end2){
            return null;
        }
        int rootData=preOrder[begin1];
        Node head=new Node(rootData);
        int divider=findIndexInArray(inOrder,rootData,begin2,end2);
        int offSet=divider-begin2-1;
        Node left=buildTreePreOrderInOrder(preOrder,begin1+1,begin1+1+offSet,inOrder,begin2,begin2+offSet);
        Node right=buildTreePreOrderInOrder(preOrder,begin1+offSet+2,end1,inOrder,divider+1,end2);
        head.left=left;
        head.right=right;
        return head;
    }
    public int findIndexInArray(int[] a,int x,int begin,int end){
        for(int i=begin;i<=end;i++){
            if(a[i]==x)return i;
        }
        return -1;
    }
    public void preOrder(Node n){
        if(n!=null){
            System.out.print(n.val+",");
            preOrder(n.left);
            preOrder(n.right);
        }
    }
    public void inOrder(Node n){
        if(n!=null){
            inOrder(n.left);
            System.out.print(n.val+",");
            inOrder(n.right);
        }
    }
}
class Node{
    Node left;
    Node right;
    int val;
    public Node(int val){
        this.val=val;
    }
    public Node getLeft(){
        return left;
    }
    public Node getRight(){
        return right;
    }
    public int getVal(){
        return val;
    }
}