【2错-2】Two Sum IV - Input is a BS

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

日期	是否一次通过	comment
2019-01-19 22:38	否	对twoSum和BST理解不够
2019-01-21 00:00	否	对twoSum和BST理解不够

image.png

（来源：https://leetcode.com/problems/two-sum-iv-input-is-a-bst/）

1. 结合BST性质方法：TODO；
2. twoSum方法：
   2.1 set存取targetVal - root.val，依次判断每个节点的val是否存在set中；
   2.2 inOrder得到BST的升序序列，再使用2 pointer求解two

2.1 set存取

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if(root == null) {
            return false;
        }
        
        Set<Integer> nodeSet = new HashSet<>();
        return helper(root, nodeSet, k);
    }
    
    private boolean helper(TreeNode root, Set<Integer> nodeSet, int k) {
        
        if(root == null) {
            return false;
        }
        
        if(nodeSet.contains(root.val)) {
                return true;
        }
            
        nodeSet.add(k-root.val);
        
        return helper(root.left, nodeSet, k) || helper(root.right, nodeSet, k);
    }
}

2.2 inOrder

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if(root == null) {
            return false;
        }
        
        List<Integer> nodeOrder = new ArrayList<>();
        inOrder(root, nodeOrder);
        
        return checkerTarget(nodeOrder, k);
    }
    
    private void inOrder(TreeNode root, List<Integer> nodeOrder) {
        if(root == null) {
            return;
        }
        
        inOrder(root.left, nodeOrder);
        nodeOrder.add(root.val);
        inOrder(root.right, nodeOrder);
    }
    
    private boolean checkerTarget(List<Integer> nodeOrder, int k ) {
        for(int i=0, j=nodeOrder.size()-1; i<j;) {
            if(nodeOrder.get(i)+nodeOrder.get(j) == k) {
                return true;
            }
            if(nodeOrder.get(i)+nodeOrder.get(j) < k) {
                i++;
            }
            if(nodeOrder.get(i)+nodeOrder.get(j) > k) {
                j--;
            }
        }
        
        return false;
        
        
    }
    
}