Easy to understand solution with one subtle difference.


  • 0
    T

    One subtle difference in this solution and other solutions is that I am counting the node instead of doing all weird math.

    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return helper(inorder, 0, inorder.length-1, preorder, 0, preorder.length-1);
        }
    
        public TreeNode helper(int[] inorder, int inSt, int inEnd,
                               int[] preorder, int preSt, int preEnd) {
            if (preSt > preEnd || inSt > inEnd){
                return null;
            }
    
            int n = preorder[preSt];
    
            TreeNode root = new TreeNode(n);
            int index = findIndex(n, inorder, inSt, inEnd);
    
            root.left = helper(inorder, inSt, inSt + index -1, preorder, preSt + 1, preSt + index);
    
            root.right = helper(inorder, inSt + index + 1, inEnd, preorder, preSt + index + 1, preEnd);
    
            return root;
        }
    
        private int findIndex(int n, int[] inorder, int inSt, int inEnd){
            int cnt = 0;
            for (int i = inSt; i <= inEnd ; i++){
                if (inorder[i] == n){
                    break;
                }
                cnt++;
            }
    
            return cnt;
        }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.