Easy java solution beats 75% of submissions O(n log n) runtime


  • 0
    D
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean findTarget(TreeNode root, int k) {
            
            //Base case: if root is null or only 1 node is present, return false
            if(root==null || root.left==null && root.right==null)
                return false;
            
            /*General case: if 1 or more nodes are present,
             Do inorder traversal and retrieve list*/
            List<Integer> numberList=new ArrayList<Integer>();
            
            inorderTraversal(numberList,root);
            
            /*Once list is obtained,iterate through the list and for each , find its complement from the target number
             traverse through the tree to see if the complement is present in it*/
            int val1=0;
            
            int val2=0;
            
            for(int i=0;i<numberList.size();i++)
            {
                 val1=numberList.get(i);
                 val2=k-val1;
                
                //if element is half of the target, continue, since the corresponding other half is not present in a BST
                if(val2==val1)
                    continue;
                
                
                if(isPresent(root,val2))
                    return true;
                     
            }
            
            return false;
            
        }
        
        //inorder traversal to obtain list of numbers in sorted order
        public void inorderTraversal(List<Integer> numberList,TreeNode root)
        {
            if(root==null)
                return;
            
            inorderTraversal(numberList,root.left);
            numberList.add(root.val);
            inorderTraversal(numberList,root.right);
        }
        
        //traverse through the tree to check if element is present
        public boolean isPresent(TreeNode root, int element)
        {
            TreeNode current=root;
            
            while(current!=null)
            {
                if(current.val==element)
                    return true;
                else if(current.val>element)
                    current=current.left;
                else
                    current=current.right;
                    
            }
            
            return false;
        }
    }
    

Log in to reply
 

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