[LeetCode] 1302. Deepest Leaves Sum

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

Deepest Leaves Sum - LeetCode

Deepest Leaves Sum - Medium

 

leaf 노드의 val들을 모두 더해주면 되는 문제다.

노드들을 방문해주며 해당 노드가 leaf인지 파악하는게 관건이다.

 

현재까지 최대 깊이 M을 0으로 선언해준다.

root 노드부터 시작하여, 노드를 방문할때마다 현재 깊이가 M과 같다면 ret에 현재 노드 val을 +해주고,

현재 깊이가 M보다 크다면 M을 현재 깊이로 바꿔주고 ret은 현재 노드 val로 세팅해준다.

그 후 왼쪽 자식이 있다면 왼쪽자식을 호출해주고 오른쪽자식도 마찬가지로 해준다.

 

전체 풀이 코드

class Solution {
public:
    int M = 0;
    int ret = 0;
    int deepestLeavesSum(TreeNode* root) {
        run(root, 0);
        return this->ret;
    }
    void run(TreeNode* node, int depth) {
        if (depth==this->M) this->ret+=node->val;
        else if (depth>this->M) this->ret=node->val, this->M = depth;
        if (node->left) run(node->left, depth+1);
        if (node->right) run(node->right, depth+1);
    }
};