[LeetCode] 513. Find Bottom Left Tree Value

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Leetcode - Find Bottom Left Tree Value

문제 유형 : 트리, dfs, 재귀

문제 난이도 : Medium

 

문제

Given the root of a binary tree, return the leftmost value in the last row of the tree.

 

이진 트리의 루트가 주어진다.

트리의 마지막 행의 가장 왼쪽 값을 반환하시오.

 

풀이

dfs를 하면서, 각 노드의 왼쪽, 오른쪽별로 더 깊이 있는 노드를 재귀적으로 반환하면 된다.

<depth, value>의 형태로 값을 반환시킨다.

같은 깊이라면, 더 왼쪽의 노드를 상위 노드에 반환한다.

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    pair<int, int> traverse(TreeNode* node, int depth) {
        if(node == nullptr) return {-1, 0};
        if(!(node -> left) && !(node -> right)) return {depth, node -> val};
        auto left = traverse(node -> left, depth+1);
        auto right = traverse(node -> right, depth+1);

        if(left.first >= right.first) return left;
        return right;
    }

    int findBottomLeftValue(TreeNode* root) {
        auto it = traverse(root, 1);
        return it.second;
    }
};