[Leetcode][Java]1315 Sum of Nodes with Even-Valued Grandparent (부모의 부모 노드가 짝수 값을 가지고 있는 노드들의 합)

Given a binary tree, return the sum of values of nodes with even-valued grandparent. 

(A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

 

binary tree가 주어지고, 부모의 부모 ( grand parent) (할아버지)의 value가  짝수인 node의 value합을 구해라 

만약, 부모의 부모의 값이 짝수인 노드가 없다면 0을 반환해라

---

dfs를 이용하여 해답을 구해보자.

dfs메서드를 호출할때, 해당 노드의 부모와 부모의 부모를 파라미터로 전달하면 특정 노드에서 해당 부모의 부모의 value를 조회할 수 있다. 

    private void dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            dfs (node.left, node, parent);
        }

        if (node.right != null) {
            dfs (node.right, node, parent);
        }
    }

 

해당 메서드를 호출하는 내역을 보자

전역 변수를 사용하여 해결하는 방법이다.

    static int rst = 0;
    public int sumEvenGrandparent(TreeNode root) {
        if (root != null) {
            dfs (root, null, null);
        }
        return rst;
    }

 

만약, 전역 변수를 사용하지 않고 메서드에서 result를 반환하고 싶은 경우에는 아래와 같이 하면 해결 가능하다.

( 위의 방법과 거의 동일하다. 메서드의 반환타입만 추가되고 해당 값을 반환해주면 된다.)

    public int sumEvenGrandparent(TreeNode root) {
        int rst = 0;
        if (root != null) {
            rst = dfs (root, null, null);
        }
        return rst;
    }
    private int dfs(TreeNode node, TreeNode parent, TreeNode grandParent) {
        
        int rst = 0;
        if (grandParent != null && grandParent.val % 2 == 0) {
            rst += node.val;
        }

        if (node.left != null) {
            rst += dfs (node.left, node, parent);
        }

        if (node.right != null) {
            rst += dfs (node.right, node, parent);
        }

        return rst;
    }