方案一、使用BFS遍历每个元素,遍历时不停检测是否存在2个元素和相加满足要求
时间O(n),空间O(n)
1 public boolean findTarget(TreeNode root, int k) { 2 if(root==null) return false; 3 Set<Integer> set = new HashSet<Integer>(); 4 Deque<TreeNode> queue = new LinkedList<TreeNode>(); 5 queue.add(root); 6 while(!queue.isEmpty()){ 7 TreeNode temp = queue.poll(); 8 // 参考两数之和,这里由于不用确定下标,使用set即可 9 if(set.contains(k-temp.val)){ 10 return true; 11 } 12 set.add(temp.val); 13 if(temp.left!=null){ 14 queue.add(temp.left); 15 } 16 if(temp.right!=null){ 17 queue.add(temp.right); 18 } 19 } 20 return false; 21 }
方案二、中序遍历一次性将所有元素取出(中序遍历的结果是非递减序列,如不存在重复元素则为递增),然后利用双指针法逐步逼近
时间O(n),空间O(n)
1 public boolean findTarget(TreeNode root, int k) { 2 List<Integer> list =new ArrayList<Integer>(); 3 // 中序遍历得出非递减数组 4 inorder(root,list); 5 int left=0,right=list.size()-1; 6 // 针对非递减数组使用双指针法逐步逼近目标值 7 while(left<right){ 8 int sum = list.get(left)+list.get(right); 9 if(sum==k){ 10 return true; 11 } 12 if(k<sum){ 13 right--; 14 }else{ 15 left++; 16 } 17 } 18 return false; 19 } 20 21 public void inorder(TreeNode root,List<Integer> list){ 22 if(root==null){ 23 return; 24 } 25 inorder(root.left,list); 26 list.add(root.val); 27 inorder(root.right,list); 28 }