Find Elements in a Contaminated Binary Tree

문제

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/description/

LeetCode - The World's Leading Online Programming Learning Platform

풀이 코드

/**
 * 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 FindElements {

    TreeNode tree;
    static boolean answer = false;

    public FindElements(TreeNode root) {
        root.val = 0;
        changeTree(root);
        tree = root;
    }
    
    public boolean find(int target) {
        answer = false;
        findTarget(tree, target);
        return answer;
    }
	
    /**
     * Tree를 순회하면서, target과 일치하면 answer를 true로 변경 후 순회를 종료한다.
     * @param node
     * @param target
     */
    private static void findTarget(TreeNode node, int target) {
        if (answer) return;
        if (node == null) {
            return;
        } else {
            if (node.val == target) {
                answer = true;
                return;
            }
            findTarget(node.left, target);
            findTarget(node.right, target);
        }
    }

    /**
     * Tree를 순회하면서, node들의 값을 변환한다.
     * @param node
     */
    private static void changeTree(TreeNode node) {
        if (node == null) {
            return;
        } else {
            if (node.left != null) node.left.val = 2 * node.val + 1;
            if (node.right != null) node.right.val = 2 * node.val + 2;
            changeTree(node.left);
            changeTree(node.right);
        }
    }
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */

입출력 예시

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True

코드 설명

• node의 값이 -1로 이루어진 Tree를 문제에서 주어진 조건대로 변환한다.

node.left가 null이 아니면, node.left.val에 2 * node.val + 1로 바꾼다.
node.right가 null이 아니면, node.right.val에 2 * node.val + 2로 바꾼다.

• 변환된 Tree의 node들의 값에 target으로 주어지는 숫자가 있으면 true를 return하고 없으면, false를 return 한다.