653. 两数之和 IV - 输入二叉搜索树

1.题目

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

提示:

• 二叉树的节点个数的范围是 [1, 104].
• -104 <= Node.val <= 104
• 题目数据保证，输入的 root 是一棵 有效 的二叉搜索树
• -105 <= k <= 105

2.示例

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

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

3.答案

①中序遍历+两数之和

将问题拆成两步，第一部得到二叉树的遍历序列，第二步检查是否存在两数之和为k. (两数之和)。
既然要得到遍历序列，对于一棵有效的二叉搜索树中序遍历的结果是一个没有重复元素的有序序列。

void inorder(TreeNode*root,vector<int> &res){  //中序遍历
        if(!root) return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    bool findTarget(TreeNode* root, int k) {
        vector<int> res;
        inorder(root,res);

        //因为不需要节点的下标，所以可以使用set存储而不是map记录下标和值的映射关系
        //只需要判断元素是否存在。
        unordered_set<int> s;
        for(int i:res){
            // find返回迭代器,count返回个数
            if(s.count(k-i)) return true; //可以再元素i前找到k-i
            s.insert(i);  //将i插入
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

②遍历的同时检查

将中序遍历与两数之和的检查结合起来。
对应元素之和是否为k，如果想要一次遍历就查找成功，就要避免相同元素的重复利用。先在之前经过的元素里查找是否可以和当前root->val构成k，找不到的话在插入root->val。此时不会利用同一个超过一次。

// 改变中序遍历的操作来检查
 bool infind(TreeNode* root,int k,unordered_set<int> &s){
        if(!root) return false;
        if(s.count(k-root->val)) return true;
        s.insert(root->val);
        return infind(root->left,k,s)||infind(root->right,k,s);
    }
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> s;
        return infind(root,k,s);
    }
1
2
3
4
5
6
7
8
9
10
11

// 利用BFS（或者树的层次遍历的同时检查）
   //遍历的顺序并不重要，重点是在先前序列里检查，在插入自身，避免元素重复利用
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> s;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            TreeNode*tmp=q.front();
            q.pop();
            if(s.count(k-tmp->val)) return true;
            s.insert(tmp->val);
            if(tmp->left) q.push(tmp->left);
            if(tmp->right) q.push(tmp->right);
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum-iv-input-is-a-bst