[LeetCode] 1214. Two Sum BSTs

Given the roots of two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:

[LeetCode] 1214. Two Sum BSTs

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.

Example 2:

[LeetCode] 1214. Two Sum BSTs

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Constraints:

  • The number of nodes in each tree is in the range [1, 5000].
  • -109 <= Node.val, target <= 109

查找两棵二叉搜索树之和。

给出两棵二叉搜索树,请你从两棵树中各找出一个节点,使得这两个节点的值之和等于目标值 Target。如果可以找到返回 True,否则返回 False

提示:

每棵树上最多有 5000 个节点。
-10^9 <= target, node.val <= 10^9

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum-bsts
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题我给出两种思路。一是利用hashset,二是利用BST的中序遍历。

hashset 的做法是,我们为这两棵树各自创建一个 hashset 来记录这两棵树里面的节点值。记录好以后,我们遍历其中一个 hashset 的值 val,并在另一个 hashset 里找是否存在 target - val,如果存在则 return true。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
18         HashSet<Integer> set1 = new HashSet<>();
19         HashSet<Integer> set2 = new HashSet<>();
20         helper(root1, set1);
21         helper(root2, set2);
22         for (int num : set1) {
23             if (set2.contains(target - num)) {
24                 return true;
25             }
26         }
27         return false;
28     }
29 
30     private void helper(TreeNode root, HashSet<Integer> set) {
31         if (root == null) {
32             return;
33         }
34         set.add(root.val);
35         helper(root.left, set);
36         helper(root.right, set);
37     }
38 }

 

BST 的中序遍历的做法是,我们为这两棵树各自创建一个 stack,我们暂且记为 stack1 和 stack2。对于 root1,我们做中序遍历,一开始不停地把左子树加入 stack1;对于 root2,我们做逆向的中序遍历,一开始不停地把右子树加入 stack2。因为 BST 在做中序遍历的时候结果是有序的,所以 root1 的遍历结果是递增的,root2 的遍历结果是递减的。如果 root1.val + root2.val < target 则需要再找 root1 中序遍历的下一个节点,因为他会使得 root1.val + root2.val 更大;反之则需要再找 root2 逆向中序遍历的下一个节点,因为他会使得 root1.val + root2.val 更小。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
18         // corner case
19         if (root1 == null || root2 == null) {
20             return false;
21         }
22 
23         // normal case
24         Deque<TreeNode> stack1 = new ArrayDeque<>();
25         Deque<TreeNode> stack2 = new ArrayDeque<>();
26         TreeNode t1;
27         TreeNode t2;
28         while (true) {
29             while (root1 != null) {
30                 stack1.push(root1);
31                 root1 = root1.left;
32             }
33             while (root2 != null) {
34                 stack2.push(root2);
35                 root2 = root2.right;
36             }
37             if (stack1.isEmpty() || stack2.isEmpty()) {
38                 break;
39             }
40 
41             t1 = stack1.peek();
42             t2 = stack2.peek();
43             if (t1.val + t2.val == target) {
44                 return true;
45             }
46             // inorder traversal for root1
47             else if (t1.val + t2.val < target) {
48                 stack1.pop();
49                 root1 = t1.right;
50             }
51             // inorder traversal for root2
52             else {
53                 stack2.pop();
54                 root2 = t2.left;
55             }
56         }
57         return false;
58     }
59 }

 

LeetCode 题目总结

上一篇:LeetCode - Easy - 872. Leaf-Similar Trees


下一篇:CS144 lab4 TCPConnection实现笔记