脚撕LeetCode(653)Easy

用户6203048

发布于 2022-01-18 08:18:32

1330

发布于 2022-01-18 08:18:32

文章被收录于专栏：JathonKatu JathonKatuJathonKatu

题目地址：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/solution/

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

输入:   
     5   
    / \ 
  3   6
 / \     \ 
2   4   7 
Target = 9 
输出: True 
案例 2: 
输入:   
     5   
    / \ 
  3   6
  / \   \ 
2   4   7
Target = 28 
输出: False

这道题涉及到了二叉搜索树（二叉查找树、二叉排序树，我们先复习一下二叉搜索树）

它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

二叉查找树还有一个很大的优点我们在501题中讲到过，二叉查找树的中序遍历一定是升序

那么，我们可以知道二叉搜索树的特点了，接下来我们开始做题：

一、爆破法

中序遍历先将二叉树挪动到一个list中，然后启动双指针左右两端，和k相比，如果大于则右指针左移，如果小于则左指针右移动，直到我们的左右指针相交或者找到值

执行结果如下：

422 / 422 个通过测试用例

状态：通过

执行用时: 3 ms

内存消耗: 39.8 MB

public boolean findTarget(TreeNode root, int k) {
        // 中序遍历的查找二叉树一定是升序，所以我们把他放进list中
        List<Integer> list = new ArrayList<>();
        inList(root,list);
        int right = list.size() - 1 ;
        int left = 0;
        int ans;
        while (right > left) {
            ans = list.get(left) + list.get(right);
            if (ans == k) {
                return true;
            } else if (ans > k) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
    public void inList(TreeNode root, List<Integer> list) {
        if (null == root) return;
        inList(root.left, list);
        list.add(root.val);
        inList(root.right, list);
    }

当然还有一种做法，就是用hashset或者hashMap，之前在做两数之和的时候用过，这里主要用到的是二叉查找树的优点，就不在这里铺开这种爆破法了

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-06-11，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树