当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST

LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST

题目描述

653 Two Sum IV - Input is a BST
https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input:
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

相似题目

LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和


解题过程

two sum 问题的变种,输入是一个BST,没想到如何使用BST的性质,写了个适用所有二叉树的。
时间复杂度 O(n),空间复杂度 O(n)
官方题解中,前两个方法也都没用BST的性质,最后一个解法,先把BST中序遍历为升序数组,然后使用左右双指针O(n)遍历,也是一种思路。
总的来说还是递归遍历加map更简单。

private static class SolutionV2020 {
    public boolean findTarget(TreeNode root, int k) {
        Map<Integer, Boolean> map = new HashMap<>();
        return preOrderTraverse(root, k, map);
    }

    private boolean preOrderTraverse(TreeNode root, int k, Map<Integer, Boolean> map) {
        if (null == root) {
            return false;
        }
        if (map.containsKey(k - root.val)) {
            return true;
        }
        map.put(root.val, false);
        return preOrderTraverse(root.left, k, map) || preOrderTraverse(root.right, k, map);
    }
}

GitHub代码

algorithms/leetcode/leetcode/_653_TwoSum4BST.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_653_TwoSum4BST.java


上一篇 LeetCode.669.Trim a Binary Search Tree 修剪二叉搜索树BST

下一篇 LeetCode.637.Average of Levels in Binary Tree 二叉树的层平均值

阅读
评论
349
阅读预计1分钟
创建日期 2020-01-31
修改日期 2020-01-31
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论