JAVA二叉樹前序，中序，後序周遊及使用遞歸還原二叉樹

二叉樹的前序，中序，後序周遊規則

Tree Traversals:

前序周遊（preorder）：根節點–>左子樹–>右子樹

中序周遊（inorder）：左子樹–>根節點–>右子樹

後續周遊（postorder）：左子樹–>右子樹–>根節點

Tips:這裡我把對應的英文寫出來，大家可以在命名變量的時候使用

現在我們舉一個執行個體供大家了解：

前序周遊：a–>b–>d–>e–>f–>g–>c

中序周遊：d–>e–>b–>g–>f–>a–>c

後序周遊：e–>d–>g–>f–>b–>c–>a

關于周遊的使用以及還原二叉樹執行個體

輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹。假設輸入的前序周遊和中序周遊的結果中都不含重複的數字。例如輸入前序周遊序列{1,2,4,7,3,5,6,8}和中序周遊序列{4,7,2,1,5,3,8,6}，則重建二叉樹并傳回。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre==null||in==null){
            return null;
        }
        TreeNode root = constructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
        return root;
    }
    
    private TreeNode constructBinaryTree(int [] pre, int preStart, int preEnd, int [] in, int inStart, int inEnd){
        if(preStart>preEnd||inStart>inEnd){
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==pre[preStart]){
                root.left = constructBinaryTree(pre, preStart+1, preStart+i-inStart, in, inStart, i-1);
                root.right = constructBinaryTree(pre, preStart+i-inStart+1, preEnd,in, i+1, inEnd);
                break;
            }
        }
        return root;
    }
}
           

解析：這道題來自于劍指offer。這個代碼比較好的運用了遞歸的思想。通過前序中序周遊來确定左右子樹及其節點數，進而可以确定每個子樹中節點的index，通過遞歸建立出樹。

Tips:前序周遊的第一個點即為中序周遊中左右子樹的分隔點。