Leetcode之653-两数之和IV-输入BST(Two Su

前言

个人网站

公众号: 北京程序猿, 网站 : https://yaml.vip

算法题

题干

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

示例

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

Target = 9

输出: True

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

Target = 28

输出: False

解法

1. 考虑BST这个条件，中序遍历有序，转化为有序数组两数之和问题
2. 不考虑BST这个条件，在递归过程中通过中间变量存储所有节点值，转化为非有序数组两数之和问题

Java代码

/**
  * 解法1: 中序遍历+双指针
  */
public boolean findTarget(TreeNode root, int k) {
    List<TreeNode> inOrderList = new ArrayList<>();
    inOrderTraversal(root, inOrderList);
    Integer[] array = inOrderList.stream().map(x -> x.val).toArray(Integer[]::new);
    if (array == null || array.length <= 1) {
        return false;
    }
    final int length = array.length;
    int frontCursor = 0, backCursor = length - 1;
    while (frontCursor < backCursor) {
        int frontValue = array[frontCursor];
        int minusValue = k - array[backCursor];
        if (frontValue == minusValue) {
            return true;
        }
        if (frontValue < minusValue) {
            frontCursor++;
            continue;
        }
        backCursor--;
    }
    return false;
}

public void inOrderTraversal(TreeNode root, List<TreeNode> list) {
    if (root == null) {
        return;
    }
    inOrderTraversal(root.left, list);
    list.add(root);
    inOrderTraversal(root.right, list);
}

/**
  * 解法2: 递归过程中存储所有节点值
  */
public boolean findTarget2(TreeNode root, int k) {
    return existTarget(root, k, new HashSet<>(64));
}

public boolean existTarget(TreeNode root, int k, Set<Integer> set) {
    if (root == null) {
        return false;
    }
    if (set.contains(k - root.val)) {
        return true;
    }
    set.add(root.val);
    return existTarget(root.left, k, set) || existTarget(root.right, k, set);
}

思考题

1. 上述两种解法时间复杂度和空间复杂度分别是多少？
2. 面试过程中给面试官呈现哪种解法比较好？为何？

本文著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请于文首标明作者姓名，保持文章完整性，并附上出处和文章链接！未按规范转载者，作者保留追究相应责任的权利！

作者：北京程序猿

链接：https://yaml.vip/2019/03/05/Leetcode%E4%B9%8B653-%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8CIV-%E8%BE%93%E5%85%A5BST/