一.先序中序建樹(shù)

image.png

思路：根據(jù)先序遍歷數(shù)組的元素從左到右確定根結(jié)點(diǎn)，先構(gòu)建左子樹(shù)后構(gòu)建右子樹(shù)缕溉。
中序遍歷數(shù)組確定左右子樹(shù)以及左右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。

class TreeNode{
    public int val;
    public TreeNode left = null;
    public TreeNode right = null;

    TreeNode(int val){
        this.val = val;
    }
}

public class Solution {
    public TreeNode recreateTree(int [] pre,int [] in, int preBegin, int preEnd,
                                 int inBegin, int inEnd){
        if (preBegin > preEnd){return null;}

        TreeNode root = new TreeNode(pre[preBegin]);

        int k = inBegin;

        while (in[k] != pre[preBegin]){
            k++;
        }

        root.left = recreateTree(pre, in, preBegin + 1, preBegin + k - inBegin, inBegin, k - 1);
        root.right = recreateTree(pre, in, preEnd - inEnd + k + 1, preEnd, k + 1, inEnd);
        return root;
    }

    public void printIn(TreeNode root){
        if (root == null){return;}
        printIn(root.left);
        System.out.print(root.val + " ");
        printIn(root.right);
    }

    public void printPost(TreeNode root){
        if (root == null){return;}
        printPost(root.left);
        printPost(root.right);
        System.out.print(root.val + " ");
    }

    public void printPre(TreeNode root){
        if (root == null){return;}
        System.out.print(root.val + " ");
        printPre(root.left);
        printPre(root.right);
    }

    public static void main(String[] args){
       int[] pre = {1, 3, 6, 7, 5, 8, 4};
       int[] in = {6, 3, 7, 1, 8, 4, 5};

       TreeNode root = new Solution().recreateTree(pre, in, 0, 6, 0, 6);
       System.out.print("先序遍歷：");
       new Solution().printPre(root);
       System.out.println();
       System.out.print("中序遍歷：");
       new Solution().printIn(root);
        System.out.println();

        System.out.print("后序遍歷：");
       new Solution().printPost(root);
        System.out.println();
    }
}

image.png

二.后序中序建樹(shù)

image.png

思路：根據(jù)后序遍歷數(shù)組的元素從右到左確定根結(jié)點(diǎn)吃型，并且先構(gòu)建右子樹(shù)证鸥，后構(gòu)建左子樹(shù)。
中序遍歷數(shù)組確定左右子樹(shù)以及左右子樹(shù)的節(jié)點(diǎn)個(gè)數(shù)勤晚。

class TreeNode{
    int val;
    TreeNode left = null;
    TreeNode right = null;

    TreeNode(int val){
        this.val = val;
    }
}

public class Solution {
    public TreeNode createTree(int[] in, int[] post, int inBegin, int inEnd, int postBegin, int postEnd){
        if (postEnd < postBegin){return null;}

        int k = inBegin;

        while (in[k] != post[postEnd]){
            k++;
        }

        TreeNode root = new TreeNode(post[postEnd]);        //k - inBegin

        root.right = createTree(in, post, k + 1, inEnd, postEnd + k - inEnd, postEnd-1);
        root.left = createTree(in, post, inBegin, k - 1, postBegin, postBegin + k - inBegin - 1);
        return root;
    }

    public void printIn(TreeNode root){
        if (root == null){return;}
        printIn(root.left);
        System.out.print(root.val + " ");
        printIn(root.right);
    }

    public void printPost(TreeNode root){
        if (root == null){return;}
        printPost(root.left);
        printPost(root.right);
        System.out.print(root.val + " ");
    }

    public void printPre(TreeNode root){
        if (root == null){return;}
        System.out.print(root.val + " ");
        printPre(root.left);
        printPre(root.right);
    }

    public static void main(String[] args){
       int[] in = {6, 3, 7, 1, 8, 4, 5};
       int[] post = {6, 7, 3, 4, 8, 5, 1};

       TreeNode root = new Solution().createTree(in, post, 0, 6, 0, 6);
       System.out.print("先序遍歷：");
       new Solution().printPre(root);
       System.out.println();
       System.out.print("中序遍歷：");
       new Solution().printIn(root);
        System.out.println();

        System.out.print("后序遍歷：");
       new Solution().printPost(root);
        System.out.println();
    }
}

image.png