1. HashSet

    添加 add
    是否存在 contains
    删除 remove
    清空 clear

    1. public boolean dfs(TreeNode root, int target) {
    2.     if (root == null) return false;
    3.     if (set.contains(target - root.val)) return true;
    4.     else set.add(root.val);
    6.     return dfs(root.left, target) || dfs(root.right, target);
    8.     }
    1. 双指针法 搜索树中序遍历

    利用bst特性
    ArrayDeque
    在队列尾插入addLast
    取出队列尾，不删除peekLast
    取出队列尾并删除pollLast

    1. public boolean findTarget(TreeNode root, int k) {
    2.         Deque<TreeNode> leftdeque = new ArrayDeque<>(), rightdeque = new ArrayDeque<>();
    3.         leftdeque.addLast(root);
    4.         TreeNode node = root;
    5.         while (node != null) {
    6.             leftdeque.addLast(node);
    7.             node = node.left;
    8.         }
    9.         node = root;
    10.         while (node != null) {
    11.             rightdeque.addLast(node);
    12.             node = node.right;
    13.         }
    14.         TreeNode l = leftdeque.peekLast(), r = rightdeque.peekLast();
    15.         while (l.val < r.val) {
    16.             int t = l.val + r.val;
    17.             if (t == k) return true;
    18.             if (t < k) l = getNext(leftdeque, true);
    19.             else r = getNext(rightdeque, false);
    21.         }
    22.         return false;
    26.     }
    27.     public TreeNode getNext(Deque<TreeNode> deque, boolean flag) {
    28.         TreeNode node = flag ? deque.pollLast().right : deque.pollLast().left;
    29.         while (node != null) {
    30.             deque.addLast(node);
    31.             node = flag ? node.left : node.right;
    32.         }
    33.         return deque.peekLast();
    34.     }