653. 两数之和 IV - 输入 BST

题目描述

题解分析

最简单的方法就是遍历整棵树，找出所有可能的组合，判断是否存在和为 kk 的一对节点。现在在此基础上做一些改进。

如果存在两个元素之和为 k，即 x+y=k，并且已知 x 是树上一个节点的值，则只需判断树上是否存在一个值为 y 的节点，使得 y=k-x。基于这种思想，在树的每个节点上遍历它的两棵子树（左子树和右子树），寻找另外一个匹配的数。在遍历过程中，将每个节点的值都放到一个 set 中。

对于每个值为 p 的节点，在 set 中检查是否存在 k−p。如果存在，那么可以在该树上找到两个节点的和为 k；否则，将 p 放入到 set 中。

如果遍历完整棵树都没有找到一对节点和为 k，那么该树上不存在两个和为 k 的节点。

代码实现

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    Set<Integer> set = new HashSet<>();

    public boolean findTarget(TreeNode root, int k) {

        if(root == null)

            return false;

        if(set.contains(k-root.val))

            return true;

        set.add(root.val);

        return findTarget(root.left, k) || findTarget(root.right, k);

    }

}

复杂度分析

时间复杂度：O(n)，其中 N 是节点的数量。最坏的情况下，整棵树被遍历一次。
空间复杂度：O(n)。最坏的情况下，set 存储 n 个节点的值。

巴特西

653. 两数之和 IV - 输入 BST + HashSet

653. 两数之和 IV - 输入 BST

题目描述

题解分析

代码实现

复杂度分析

最新文章

热门文章