原文鏈接：http://blog.csdn.net/qq_22329521/article/details/52948072
二叉樹的遍歷常見方式

enter image description here

• 前序遍歷，先訪問跟節(jié)點(diǎn)，在訪問子結(jié)點(diǎn)，最后訪問右子結(jié)點(diǎn)順序是abdefgc
• 中序遍歷，先訪問左子結(jié)點(diǎn)，再訪問根結(jié)點(diǎn)宪睹，最后訪問右子結(jié)點(diǎn)debgfac
• 后序遍歷，先訪問左子結(jié)點(diǎn)蚕钦，在訪問右子結(jié)點(diǎn)亭病，最后訪問更結(jié)點(diǎn)edgfbca
• 寬度優(yōu)先遍歷，先訪問樹的第一層結(jié)點(diǎn)嘶居，再訪問樹的第二層結(jié)點(diǎn)罪帖，一致到訪問到最下面一層結(jié)點(diǎn)，同一層結(jié)點(diǎn)邮屁，從左到右一次遍歷abcdfeg

重構(gòu)二叉樹

輸入二叉樹的前序遍歷和中序遍歷都不含重復(fù)數(shù)字整袁，重建該二叉樹
思路：已知前序找根結(jié)點(diǎn)，然后判斷跟結(jié)點(diǎn)在中序輸出中的位置佑吝，根節(jié)點(diǎn)左邊的就是左子樹坐昙，右邊就是右子樹，遞歸查找

 public static void test4() {
        int[] frontOrder = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = {4, 7, 2, 1, 5, 3, 8, 6};
        BinaryTreeNode root = BinaryTree(frontOrder, inOrder);
        printPostOrder(root);
    }

    public static void printPostOrder(BinaryTreeNode root) {
        if (root != null) {
            printPostOrder(root.getLeft());
            printPostOrder(root.getRight());
            System.out.println(root.getValue());
        }
    }

    public static BinaryTreeNode BinaryTree(int[] frontOrder, int[] inOrder) {
        //根據(jù)前序結(jié)點(diǎn)獲取當(dāng)前的跟結(jié)點(diǎn)
        BinaryTreeNode root = new BinaryTreeNode(frontOrder[0]);
        root.setLeft(null);
        root.setRight(null);
        int leftLength = 0;
        //從中序結(jié)點(diǎn)中獲取前序結(jié)點(diǎn)這個(gè)數(shù)所在的位置芋忿，因?yàn)橹行蚪Y(jié)點(diǎn)中左側(cè)是左字?jǐn)?shù)炸客，右側(cè)是右字?jǐn)?shù)
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == root.getValue()) {
                break;
            } else {
                leftLength++;
            }
        }
        //獲取右子樹的個(gè)數(shù)
        int rightLength = inOrder.length - leftLength - 1;
        if (leftLength > 0) {
            //再次初始化左側(cè)的左子樹
            int[] leftFrontOrder = new int[leftLength];
            int[] leftInorder = new int[leftLength];
            for (int j = 0; j < leftLength; j++) {
                //因?yàn)榈谝粋€(gè)被取走了
                leftFrontOrder[j] = frontOrder[j + 1];
                leftInorder[j] = inOrder[j];
            }
            BinaryTreeNode leftRoot = BinaryTree(leftFrontOrder, leftInorder);
            root.setLeft(leftRoot);
        }
        //再次初始化右側(cè)的右子樹
        if (rightLength > 0) {
            int[] rightFrontOrder = new int[rightLength];
            int[] rightInorder = new int[rightLength];
            for (int k = 0; k < rightLength; k++) {
                rightFrontOrder[k] = frontOrder[k + 1 + leftLength];
                rightInorder[k] = inOrder[k + 1 + leftLength];
            }
            BinaryTreeNode rightRoot = BinaryTree(rightFrontOrder, rightInorder);
            root.setRight(rightRoot);
        }
        return root;
    }

public class BinaryTreeNode {
    private int value;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    public BinaryTreeNode(int value){
        this.value = value;
    }
    public BinaryTreeNode(int value,BinaryTreeNode left,BinaryTreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public int getValue( ){
        return this.value;
    }
    public void setValue(BinaryTreeNode node){
        this.value = value;
    }
    public void  setLeft(BinaryTreeNode node){
        this.left = node;
    }
    public void  setRight(BinaryTreeNode node){
        this.right = node;
    }
    public BinaryTreeNode getLeft( ){
        return this.left;
    }
    public BinaryTreeNode getRight( ){
        return this.right;
    }
}