689 · Two Sum IV - Input is a BST - LintCode

# Description

Given a binary search tree and a number n , find two numbers in the tree that sums equal to n . Return null if solution cannot be found.

# Example

样例 1

输入：
{4,2,5,1,3}
3
输出： [1,2] (or [2,1])
解释：
二叉搜索树如下：
    4
   / \
  2   5
 / \
1   3

样例 2

输入：
{4,2,5,1,3}
5
输出： [2,3] (or [3,2] or [1,4] or [4,1])

這題還可以要求用 O (1) space

不是 O (1) extra space

	public class Solution {

	int[] res = new int[2];

	public int[] twoSum(TreeNode root, int n) {
	if (root == null) return null;
	Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	inorder(root, n, map);
	return res;
	}
	private void inorder(TreeNode node, int n, Map<Integer, Integer> map) {
	if (node == null) return;
	inorder(node.left, n, map);
	inorder(node.right, n, map);
	if (map.containsKey(node.val)) {
	res[0] = map.get(node.val);
	res[1] = node.val;
	} else {
	map.put(n - node.val, node.val);
	}
	}
	}