Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:
5
/ 3 6
/ \ 2 4 7
Target = 9
Output: True
Example 2:
Input:
5
/ 3 6
/ \ 2 4 7
Target = 28
Output: False
题意：给定一棵二叉查找树和一个目标值target，判断BST中是否存在两个元素使其相加和为target
思路：用深度优先搜索，将二叉树中的所有节点值放入ArrayList，然后判断是否存在相加为target的两个元素，实现如下：
public boolean findTarget(TreeNode root, int k) { List<Integer> nodes = new ArrayList<>(); dfs(root, nodes); for(int i = 0; i < nodes.size(); i++){ int val = nodes.get(i); if(nodes.contains(k - val) && k - val != val) return true; } return false; } public void dfs(TreeNode root, List<Integer> nodes){ if(root != null){ nodes.add(root.val); dfs(root.left, nodes); dfs(root.right, nodes); } }
LeetCode 653. Two Sum IV - Input is a BST
原文：http://www.cnblogs.com/zeroingToOne/p/7979083.html