653. Two Sum IV - Input is a BST

题目描述和难度

  • 题目描述：

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

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True

 

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False

 

思路分析

求解关键：这道问题是 LeetCode 第 1 题和第 167 题的扩展，我们可以分别利用它们两道题的思路来完成。

1、采用中序遍历（利用到了二分搜索树的有序性）； 2、如果借助哈希表，各种遍历方式就都可以了（没有利用到二分搜索树的有序性）。

参考解答

参考解答1

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        List<Integer> list = new ArrayList<>();
        // 使用中序遍历，得到一个顺序数组
        inOrder(root, list);
        int len = list.size();
        int l = 0;
        int r = len - 1;

        // 在顺序数组中，使用二分查找法
        while (l < r) {
            int sum = list.get(l) + list.get(r);

            if (sum > k) {
                r--;
            } else if (sum < k) {
                l++;
            } else {
                assert sum == k;
                return true;
            }
        }
        return false;
    }

    private void inOrder(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }
}

参考解答2

import java.util.HashSet;

/**
 * @author liwei
 * @date 18/6/22 下午2:18
 */
public class Solution2 {

    /**
     * 哈希表的方式，其实前中后序都能通过，甚至层序遍历也行
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) {
            return false;
        }
        // 因为 BST 中所有的数字都是不相同的，所以可以使用 Set
        HashSet<Integer> set = new HashSet<>();
        boolean[] res = new boolean[1];
        preOrder(root, set, k, res);
        return res[0];
    }

    private void preOrder(TreeNode node, HashSet<Integer> set, int k, boolean[] res) {
        if (node == null) {
            return;
        }
        // 2 * node.val == k 的情况，因为 BST 中，所有的数都不相同（即 k 的一半这个数一定不是我们要找的 ）
        if (set.contains(k - node.val) && 2 * node.val != k) {
            res[0] = true;
            return;
        } else {
            set.add(node.val);
        }
        preOrder(node.left, set, k, res);
        preOrder(node.right, set, k, res);
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0653-two-sum-iv-input-is-a-bst ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。