1022_java.md

1022. Sum of Root To Leaf Binary Numbers

Summary

🙇‍♂️ URL : https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/
🤷‍♂️ Difficulty: Easy
💆‍♂️ Submissions

• RunTime: 1 ms, faster than 47.95% of Java online submissions
• Memory Usage: 38.7 MB, less than 40.20% of Java online submissions

Source code

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

    ArrayList<String> list = new ArrayList<>();

    public int sumRootToLeaf(TreeNode root) {
        int result = 0;
        preOrderTraversal(root, "");

        for(int i=0; i<list.size(); i++) {
            result += Integer.parseInt(list.get(i), 2);
        }

        return result;
    }

    public void preOrderTraversal(TreeNode node, String value) {
        if (node != null) {
            value += Integer.toString(node.val);
            preOrderTraversal(node.left, value);
            preOrderTraversal(node.right, value);
            if(node.left == null && node.right == null) list.add(value); 
        } 
    }
}

How to Approach

트리 구조에 대한 이해가 부족하다고 느껴서 Easy부터 개념을 다시 잡기 위해 풀어보기 시작했다.
문제는 전위순회(자식보다 현재 노드를 먼저 방문하는 방식)를 사용해야 하는데, 가장 마지막(해당 노드로부터 왼쪽과 오른쪽 가지가 없는 경우) 시점까지의 모든 노드 값을 묶어서 이 값들을 2진수로 변환하여 더해주어야 한다.
만약 node == null인 시점에 모여진 값을 출력한다면 왼쪽 가지와 오른쪽 가지로 이동한 시점 각각에 모두 출력되기 때문에 동일한 값이 두번씩 출력된다.