leetcode 653. Two Sum IV - Input is a BST
LeetCode is input sum two IV BST
2023-09-14 09:11:53 时间
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
相关文章
- ☆打卡算法☆LeetCode 220. 存在重复元素 III 算法解析
- LeetCode笔记:Weekly Contest 302
- 【LeetCode】均等概率问题,我有妙招!
- LeetCode排序链表C++解法(详解)
- LeetCode 561. 数组拆分 I
- 前端工程师leetcode算法面试必备-二分搜索算法(下)
- LeetCode笔记:Biweekly Contest 90
- 【Day 01】力扣(LeetCode)每日一刷[506.相对名次][264.丑数][23.合并N个升序链表]
- leetcode刷题(126)——1289. 下降路径最小和 II
- 【动态规划】LeetCode 题解:416-分割等和子集
- JavaScript刷LeetCode拿offer-树的遍历
- LeetCode-448-找到所有数组中消失的数字
- 每日一道leetcode:7. 整数反转
- LeetCode | 子集
- LeetCode(一)——无重复字符的最长子串
- Oracle AS与IS的比较(oracleas和is)
- 深入理解Oracle中IS关键字的含义(oracle中is的意思)