653.两数之和IV-输入二叉搜索树-创新互联

文章目录

• 1.题目
• 2.示例
• 3.答案
• • ①中序遍历+两数之和
  • ②遍历的同时检查

创新互联公司主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、响应式网站建设、程序开发、网站优化、微网站、重庆小程序开发公司等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的成都网站设计、成都做网站、网站设计、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体。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

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

3.答案 ①中序遍历+两数之和

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

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

        //因为不需要节点的下标，所以可以使用set存储而不是map记录下标和值的映射关系
        //只需要判断元素是否存在。
        unordered_sets;
        for(int i:res){// find返回迭代器,count返回个数
            if(s.count(k-i)) return true; //可以再元素i前找到k-i
            s.insert(i);  //将i插入
        }
        return false;
    }

②遍历的同时检查

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

// 改变中序遍历的操作来检查
 bool infind(TreeNode* root,int k,unordered_set&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_sets;
        return infind(root,k,s);
    }

// 利用BFS（或者树的层次遍历的同时检查）
   //遍历的顺序并不重要，重点是在先前序列里检查，在插入自身，避免元素重复利用
    bool findTarget(TreeNode* root, int k) {unordered_sets;
        queueq;
        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;
    }

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

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：653.两数之和IV-输入二叉搜索树-创新互联
标题来源：http://cxhlcq.com/article/ipisi.html