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 7Target = 9Output: True
Example 2:
Input: 5 / \ 3 6 / \ \2 4 7Target = 28Output: False 解法1:使用dfs还原tree为一个sorted array，然后使用two sum算法求解。
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ # use DFS, transform tree to ordered array. def dfs(node, stack): if not node: return dfs(node.left, stack) stack.append(node.val) dfs(node.right, stack) stack = [] dfs(root, stack) i, j = 0, len(stack)-1 while i < j: if stack[i] + stack[j] == k: return True elif stack[i] + stack[j] > k: j -= 1 else: i += 1 return False
解法2:
上述算法使用迭代，
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ # use DFS, transform tree to ordered array. def dfs(node, arr): if not node: return stack = [] while node: stack.append(node) node = node.left while stack: node = stack.pop() arr.append(node.val) node = node.right while node: stack.append(node) node = node.left stack = [] dfs(root, stack) i, j = 0, len(stack)-1 while i < j: if stack[i] + stack[j] == k: return True elif stack[i] + stack[j] > k: j -= 1 else: i += 1 return False
解法3:
迭代tree，使用hash：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ # use DFS, hash record accessed node. arr = set() def dfs(node, arr): if not node: return False if k-node.val in arr: return True arr.add(node.val) return dfs(node.left, arr) or dfs(node.right, arr) return dfs(root, arr)
Method 4.
The idea is to use binary search method. For each node, we check ifk - node.val exists in this BST. Time Complexity: O(nlogn), Space Complexity: O(h). h is the height of the tree, which is logn at best case, and n at worst case.
Java version:
public boolean findTarget(TreeNode root, int k) { return dfs(root, root, k); } public boolean dfs(TreeNode root, TreeNode cur, int k){ if(cur == null)return false; return search(root, cur, k - cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k); } public boolean search(TreeNode root, TreeNode cur, int value){ if(root == null)return false; return (root.val == value) && (root != cur) || (root.val < value) && search(root.right, cur, value) || (root.val > value) && search(root.left, cur, value); }
解法5：从min到max迭代tree node，从max 到min迭代tree node：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ # iterate tree node from min to max # iterate tree node from max to min # check two node of sum == k def add_node(stack, node, is_left=True): while node: stack.append(node) node = node.left if is_left else node.right if not root: return False stack1, stack2 = [], [] add_node(stack1, root, True) add_node(stack2, root, False) while stack1 and stack2: node1 = stack1[-1] node2 = stack2[-1] if node1 is node2: return False if node1.val + node2.val == k: return True elif node1.val + node2.val > k: node2 = stack2.pop() add_node(stack2, node2.left, False) else: node1 = stack1.pop() add_node(stack1, node1.right, True) return False