Leetcode 23th August

Two Sum IV - Input is a BST

이 문제는 Tree에서 두개를 선택해서 합이 K가 되는 경우의수가 존재하는지 확인하는 문제입니다.

This problem is checking condition that when you choose the two element in tree the sum of the elements value are same as K

이경우 저는 일단 Tree을 순회하면서 값을 List에 추가한 후에 이중 for loop를 통해 두개의 합이 k가 되는 값이 있는지 체크 하는 방법을 사용했습니다.

for this case, first of all i gathering a every elements value in tree use dfs algorithm, then try to found a has a case that the sum of two elements is same as k

Java

/**
 * 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 {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> pq = new LinkedList<>();
        pq.add(root);
        while(pq.size() > 0) {
            TreeNode q = pq.poll();
            list.add(q.val);
            if (q.left != null) {
                pq.add(q.left);
            }
            if (q.right != null) {
                pq.add(q.right);
            }
        }
        for (int i =0; i < list.size() -1; i ++)
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(i) + list.get(j) == k)
                    return true;                
            }

        return false;
    }
}