Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

653. Two Sum IV - Input is a BST

給予一個二元搜尋樹和一個數字k，若存在兩數相加為k返回true。

Example：
https://assets.leetcode.com/uploads/2020/09/21/sum_tree_1.jpg
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

思路：
1.DFS然後把訪問完的節點放入HashTable裡（這裡用Set）
2.每次都檢查Set裡有沒有 k - root.val 有的話返回true，否則都返回false

Java Code：
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> set = new HashSet<>();
        return findTarget(root, k, set);
    }
    private boolean findTarget(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 findTarget(root.left, k, set) || findTarget(root.right, k,
set);
    }
}

我這輩子只寫的出Two Sum了= =

--
https://i.imgur.com/JV2r1km.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665295865.A.9EE.html
推 wu10200512: 我還不會two sum :(
推 SecondRun: 大師