653. 两数之和 IV - 输入 BST

Posted on | In
Words count in article: 222 | Reading time ≈ 1

题目

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例1：

1
2
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例2：

1
2
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示：

  1. 二叉树的节点个数的范围是 [1, 104].
  2. -104 <= Node.val <= 104
  3. root 为二叉搜索树
  4. -105 <= k <= 105

解法

解法一：

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean findTarget(TreeNode root, int k) {
        List<Integer> nums = new ArrayList<>();
        travel(root, nums);
        int begin = 0;
        int end = nums.size() - 1;
        while (begin < end) {
            if (nums.get(begin) + nums.get(end) > k) {
                begin++;
            } else if (nums.get(begin) + nums.get(end) < k) {
                end--;
            } else {
                return true;
            }
        }
        return false;
    }

    private void travel(TreeNode root, List<Integer> nums) {
        if (null == root) {
            return;
        }
        
        travel(root.right, nums);
        nums.add(root.val);
        travel(root.left, nums);
    }
0%