您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

Leetcode每日一题 653. 两数之和 IV - 输入 BST 树的遍历+哈希Set / 根据BST的中序遍历有序特性

📖本篇内容:Leetcode每日一题 653. 两数之和 IV - 输入 BST 树的遍历+哈希Set / 根据BST的中序遍历有序特性

📑 文章专栏:leetcode每日一题《打卡日常》

📆 最近更新:2022 年 3 月 19日 Leetcode每日一题 606. 根据二叉树创建字符串 DFS遍历二叉树的理解题

⭐算法仓库:小付的算法之路——Alascanfu-algorithm.git.io

🙊个人简介:一只二本院校在读的大三程序猿,本着注重基础,打卡算法,分享技术作为个人的经验总结性的博文博主,虽然可能有时会犯懒,但是还是会坚持下去的,如果你很喜欢博文的话,建议看下面一行~(疯狂暗示QwQ)

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 关爱程序猿,从你我做起

文章目录

  • 🙊写在前面🙊
  • 题目
    • 提示
    • 📝思路📝
    • ⭐代码实现⭐
    • 运行结果
  • 🙊写在最后🙊

🙊写在前面🙊

昨天休息啦~周赛模块暂更一段时间,准备面试的一些东西,后面再更哦!但是还是要去打的。来刷今天的题啦

题目

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

示例1:
在这里插入图片描述

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

示例2:
在这里插入图片描述

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

提示

  • 二叉树的节点个数的范围是 [1, 1 0 4 10^4 104].
  • − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 104<=Node.val<=104
  • root 为二叉搜索树
  • − 1 0 5 < = k < = 1 0 5 -10^5 <= k <= 10^5 105<=k<=105

📝思路📝

本题考查知识点

  • 思路1:很容易就能想到的方法就是通过遍历一下该颗树用一个Set记录当前已经在树中出现的值如果遇到当前的节点可以满足在已经记录的Set中找到一个k-node.val的值则说明这棵树存在两个元素且他们的和等于给定的目标结果

利用BST的特性来做出本题也是可以的

三叶姐姐——双指针 + BST 中序遍历

  • 思路2:根据三叶姐姐给出的思路我们很容易就能理解这道题了,对于BST我们可以知道其中序遍历是有序的,那么如果将该树的最左链与最右链分别加入栈中,很容易知道的就是每个栈的栈顶无非BST中的最小值与最大值分别对应,然后就容易了,既然出现了最小值与最大值,如果树中存在一个值的话满足左值+右值 = k则说明可以找到,反之如果二者之和小于 k 则我们需要从左树中找到比当前指针稍大的一个数,在进行比较,反之则从右树中找到一个比当前指针所指的元素稍小的一个数。以此循环,直至左右指针碰撞,还没找到就说明当前BST中没有该元素。

⭐代码实现⭐

遍历+哈希Set

class Solution {
    Set<Integer> set = new HashSet<>();
    int k ;
    public boolean findTarget(TreeNode root, int k) {
        this.k = k;
        return preorder(root);
    }
    // 加深一遍非递归方式的前序遍历的板子书写
    boolean preorder(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        if (root == null )return false;
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node != null){
                if(node.right != null)stack.push(node.right);
                if(node.left != null )stack.push(node.left);
                stack.push(node);
                stack.push(null);
            }else {
                node = stack.pop();
                if (set.contains(k - node.val))return true;
                set.add(node.val);
            }
        }
        return false;
    }
}
  • 时间复杂度: O( n n n) n代表的是二叉树的大小
  • 空间复杂度: O( n n n) 额外构建了一个大小为n的Set空间

BST中序遍历+双指针

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Deque<TreeNode>leftDeque = new ArrayDeque<>();
        Deque<TreeNode>rightDeque = new ArrayDeque<>();
        TreeNode node = root;
        while (node!=null){
            leftDeque.addLast(node);
            node = node.left;
        }
        node = root;
        while(node!=null){
            rightDeque.addLast(node);
            node = node.right;
        }
        
        TreeNode l = leftDeque.peekLast();
        TreeNode r = rightDeque.peekLast();
        while (l.val < r.val){
            int target = l.val + r.val;
            if (target == k)return true;
            if (target < k){
                l = getNext(leftDeque,true);
            }else {
                r = getNext(rightDeque,false);
            }
        }
        return false;
    }
    // 如果当前二者的值小于 k 则需要从左子树找到一个比当前值大的值 而大于k时则需要从右子树找到一个比当前值小的值
    TreeNode getNext(Deque<TreeNode> dq ,boolean isLeft){
        TreeNode node = isLeft ? dq.pollLast().right : dq.pollLast().left;
        while (node != null){
            dq.addLast(node);
            node = isLeft ? node.left : node.right;
        }
        return dq.peekLast();
    }
}
  • 时间复杂度: O( n n n) n代表的是二叉树的大小
  • 空间复杂度: O( n n n) 额外构建了一个大小为n的Set空间

运行结果

遍历+哈希Set

在这里插入图片描述
BST中序遍历+双指针

在这里插入图片描述

🙊写在最后🙊

2022- 3- 21 今天小付打卡了哦~

美好的日出 美好的山河

都因有你存在 而璀璨 耀眼

在这里插入图片描述


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进