105. Construct Binary Tree from Preorder and Inorder Traversal

Link

Solution

找出左右子樹的範圍並以子問題的方式進行解決

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = dfs(preorder, inorder, 0, inorder.length-1);
        return root;
    }
    
    int preorderIndex = 0; //preorderIndex會被子程序修改，所以要放到global保證一致
    public TreeNode dfs(int[] preorder ,int[] inorder, int inorderStart, int inorderEnd){
        
        if(preorderIndex == preorder.length) return null;
        
        TreeNode node = new TreeNode(preorder[preorderIndex]);
        int index = findIndex(inorder, preorder[preorderIndex], inorderStart, inorderEnd);
        if(index != inorderStart){
            preorderIndex++;
            node.left = dfs(preorder, inorder, inorderStart, index-1);
        }
        if(inorderEnd != index){
            preorderIndex++;
            node.right = dfs(preorder, inorder, index+1, inorderEnd);
        }
        return node;
    }
    
    public int findIndex(int[] inorder, int num, int inorderStart, int inorderEnd){
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == num) return i;
        }
        return -1;//not found
    }
    
}