653.两数之和 IV - 输入 BST

发表于 | 分类于
字数统计: 233 | 阅读时长 ≈ 1

一、题目描述

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

案例 1:

1
2
3
4
5
6
7
8
9
10
输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

案例 2:

1
2
3
4
5
6
7
8
9
10
输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

二、题解

1.中序遍历+for嵌套

1.1 思路

  1. 使用中序遍历得到一个递增数组
  2. 遍历递增数组

1.2 代码

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
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define maxSize 10000
bool findTarget(struct TreeNode *root, int k)
{
    if (root == NULL)
        return false;
    int arr[maxSize];
    int arrTop = -1;
    struct TreeNode *stack[maxSize], *p = root;
    int stackTop = -1;
    while (stackTop != -1 || p != NULL)
    {
        while (p != NULL)
        {
            stack[++stackTop] = p;
            p = p->left;
        }
        p = stack[stackTop--];
        arr[++arrTop] = p->val;
        p = p->right;
    }
    for (int i = 0; i < arrTop; i++)
        for (int j = i + 1; j <= arrTop; j++)
            if (arr[i] + arr[j] == k)
                return true;
    return false;
}