[LeetCode] 104. Maximum Depth of Binary Tree

LeetCode - 104. Maximum Depth of Binary Tree 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/maximum-depth-of-binary-tree/

풀이

이진 트리의 최대 깊이(depth)를 구하는 문제이다. DFS 또는 BFS를 활용하여 트리의 가장 깊은 곳까지 탐색하면 되는 문제이다.

소스 코드

BFS 풀이

가장 깊은 곳까지 탐색하면 되는 문제이므로 BFS로 레벨 순회를 하여 구할 수 있다.

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int maxAns = 0;
        using node = pair<TreeNode*, int>;
        queue<node> q;
        q.push({root, 1});
        while (!q.empty()) {
            node n = q.front();
            q.pop();
            if (maxAns < n.second) {
                maxAns = n.second;
            }
            if (n.first->left != nullptr) {
                q.push({n.first->left, n.second + 1});
            }
            if (n.first->right != nullptr) {
                q.push({n.first->right, n.second + 1});
            }
        }
        return maxAns;
    }
};

DFS 풀이

DFS를 활용하여 left 또는 right의 가장 깊은 곳까지 내려가면서 depth의 최댓값을 갱신시켜서 구할 수 있다.

/**
 * 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 {
    void dfs(TreeNode* root, int depth, int& ans) {
        if (ans < depth) {
            ans = depth;
        }
        if (root->left != nullptr) {
            dfs(root->left, depth + 1, ans);
        }
        if (root->right != nullptr) {
            dfs(root->right, depth + 1, ans);
        }
    }
public:
    int maxDepth(TreeNode* root) {
        int ans = 0;
        if (root != nullptr) {
            dfs(root, 1, ans);
        }
        return ans;
    }
};