leetcode 653. Two Sum IV - Input is a BST
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
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
解法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 = None
class 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 = None
class 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 = None
class 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 if k - 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 = None
class 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
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |