기억하고싶은것들

Given the root of a binary tree, return the sum of values of its deepest leaves.

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

dfs를 이용해서 답을 구해 보자. 

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

        if (level  > maxLevel) {
            sum = 0;
            maxLevel = level;
        }

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

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

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

문제 출처 

leetcode.com/problems/deepest-leaves-sum/

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;
    }