leetCode解題報告之構造二叉樹(遞歸)

1. 首先通過preOrder序列，得到根結點root！

2. 遞歸求出root的左子樹

3. 遞歸求出root的右子樹

4. 將左子樹的根結點賦值給root.left, 右子樹的根結點賦值給root.right

AC代碼（Construct Binary Tree from Preorder and Inorder Traversal ）:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0)
            return null;
        int len = inorder.length;
        return createTreeNode(preorder,inorder,0,len-1,0);
    }
    
    public TreeNode createTreeNode(int[] preorder, int[] inorder, int inLeft, int inRight, int preIndex){
        //判斷是否為葉子結點
        if (inLeft == inRight){
            TreeNode node = new TreeNode(inorder[inLeft]);
            node.left = null;
            node.right = null;
            return node;
        }
        //把preOrder中當前下標preIndex指向的val取出
        int val = preorder[preIndex];
        int findIndex = inLeft;
        //找到val在inOrder中的位置(該子樹的根節點位置)
        while (findIndex != inRight && val != inorder[findIndex]){
            findIndex++;
        }
        
        TreeNode leftNode;
        TreeNode rightNode;
        //判斷是否有左右子樹，並創建出相應的左右子樹（如果val在inOrder中的位置下標等於inLeft，表明這個子樹是沒有左子樹的，而val在inOrder中的位置下標等於inRight，表明這個子樹沒有右子樹）
        if (findIndex == inLeft){
            leftNode = null;
        }else{
            leftNode = createTreeNode(preorder,inorder,inLeft,findIndex-1,++preIndex);
        }
        if (findIndex == inRight){
            rightNode = null;
        }else{
            rightNode = createTreeNode(preorder,inorder,findIndex+1,inRight,++preIndex);
        }
        //把左右子樹賦值給root結點
        TreeNode root = new TreeNode(val);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}

AC代碼（Construct Binary Tree from Inorder and Postorder Traversal)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int postIndex;
    public TreeNode buildTree(int[] inorder,int[] postorder) {
        if (postorder.length == 0 || inorder.length == 0)
            return null;
        int len = inorder.length;
        postIndex = postorder.length - 1;
        return createTreeNode(postorder,inorder,0,len-1);
    }
    public TreeNode createTreeNode(int[] inorder, int[] postorder, int inLeft, int inRight){
        if (inLeft == inRight){
            TreeNode node = new TreeNode(inorder[inLeft]);
            node.left = null;
            node.right = null;
            return node;
        }
        int val = postorder[postIndex];
        int findIndex = inLeft;
        while (findIndex != inRight && val != inorder[findIndex]){
            findIndex++;
        }
        TreeNode leftNode;
        TreeNode rightNode;
        
        if (findIndex == inRight){
        	rightNode = null;
        }else{
        	--postIndex;
        	rightNode = createTreeNode(inorder,postorder,findIndex+1,inRight);
        }
        
        if (findIndex == inLeft){
            leftNode = null;
        }else{
            --postIndex;
            leftNode = createTreeNode(inorder,postorder,inLeft,findIndex-1);
        }
        
        TreeNode root = new TreeNode(val);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }
}

博主算法方面比較薄弱，寫得不好，歡迎大家給我留言哈！！！