Simple Java recursive solution


  • 1
    M
    /**
      * This problem is no different from the constructing binary tree from inorder and postorder, inorder is kind of standard and we use it to build the tree and the preorder is used to find the root while building the subtree.
      * */
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if( preorder.length == 0 || preorder.length != inorder.length )
                return null;
            return constructTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }
        
        private TreeNode constructTree(int[] preorder, int preorder_start, int preorder_end, int[] inorder, int inorder_start,
                                        int inorder_end)
        {
            if( inorder_start <= inorder_end && preorder_start <= preorder_end )
            {
                TreeNode root = new TreeNode(preorder[preorder_start]);
                int index = inorder_start;
                for(; index <= inorder_end; index++)
                {
                    if( inorder[index] == preorder[preorder_start])
                        break;
                }
                root.left = constructTree(preorder, preorder_start + 1, preorder_start + (index - inorder_start), inorder, inorder_start, index - 1);
                root.right = constructTree(preorder, preorder_start + (index - inorder_start) + 1, preorder_end, inorder, index + 1, inorder_end);
                return root;
            }
            //You have reached to one end. so traverse back.
            else 
                return null;
        }
                                     
    }
    

  • 0
    A

    @mandalapusc-edu What's the running time for this algorithm?


  • 0
    M

    @akash8 The amortized cost would be O(n).


Log in to reply
 

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