問題：根據(jù)先序遍歷和中序遍歷滤灯，求解后序遍歷

思路：

• 第一步，將先序和中序字符串進(jìn)行劃分曼玩。
  先序：1--247--3568鳞骤，中序：472--1--5386，由此可見演训，數(shù)字247屬于左邊的樹結(jié)點(diǎn)弟孟，數(shù)字3568屬于右邊的樹結(jié)點(diǎn)，1屬于根結(jié)點(diǎn)
• 第二步样悟，根據(jù)第一步的規(guī)律，進(jìn)行遞歸賦值。頂點(diǎn)作為根結(jié)點(diǎn)窟她。分別設(shè)置其左右結(jié)點(diǎn)陈症，如果沒有則為Null。
• PS:substring方法傳入的第一個(gè)參數(shù)不能大于字符串長(zhǎng)度或者為負(fù)數(shù)震糖。并且當(dāng)參數(shù)相同時(shí)录肯，返回的字符串長(zhǎng)度為0。

二叉樹.png

代碼實(shí)現(xiàn)：

public class N06 {

    public static void main(String[] args) {
        String preOrder = "12473568";
        String inOrder = "47215386";
        BinaryTree binaryTree = new BinaryTree(preOrder, inOrder);
        TreeNode root = binaryTree.root;
        
        System.out.println("pre order: ");
        binaryTree.preTreeTraverse(root);
        System.out.println();
        
        System.out.println("in order: ");
        binaryTree.inTreeTraverse(root);
        System.out.println();
        
        System.out.println("post order: ");
        binaryTree.postTreeTreverse(root);
        System.out.println();
    }

}

class BinaryTree {
    TreeNode root;

    public BinaryTree(String preOrder, String inOrder) {
        if (preOrder.length() == 0)
            return;
        char key = preOrder.charAt(0);
        int index = inOrder.indexOf(key);
        root = new TreeNode(key);

        this.root.setLeftNode(new BinaryTree(preOrder.substring(1, index + 1), inOrder.substring(0, index)).root);
        this.root.setRightNode(new BinaryTree(preOrder.substring(index + 1),inOrder.substring(index+1)).root);

    }

    public void preTreeTraverse(TreeNode root) {
        //先序遍歷
        if (root != null) {
            System.out.print(root.data+"  ");
            preTreeTraverse(root.leftNode);
            preTreeTraverse(root.rightNode);

        }
    }

    public void inTreeTraverse(TreeNode root) {
        //中序遍歷
        if (root != null) {
            inTreeTraverse(root.leftNode);
            System.out.print(root.data+"  ");
            inTreeTraverse(root.rightNode);
        }
    }

    public void postTreeTreverse(TreeNode root) {
        //后序遍歷
        if (root != null) {
            postTreeTreverse(root.leftNode);
            postTreeTreverse(root.rightNode);
            System.out.print(root.getData()+"  ");
        }
        
    }
}

class TreeNode {
    char data;
    TreeNode leftNode;
    TreeNode rightNode;

    public TreeNode(char data) {
        this.data = data;
    }

    public char getData() {
        return data;
    }

    public void setData(char data) {
        this.data = data;
    }

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
}

參考

根據(jù)先序遍歷與中序遍歷構(gòu)建二叉樹