[LeetCode] 104. Maximum Depth of Binary Tree c++

• 문제

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

출처 : https://leetcode.com/problems/maximum-depth-of-binary-tree/

Input: root = [3,9,20,null,null,15,7]
Output: 3

트리의 maximum depth를 구하는 문제이다.

• 문제 해결

int maxDepth(TreeNode* root) {
    if (!root) {
        return 0;
    }
    int maxLeft = maxDepth(root->left);
    int maxRight = maxDepth(root->right);

    return max(maxLeft, maxRight) + 1;
}

LC, RC 노드의 max depth를 가지고 P(부모)의 max depth를 구하는 재귀함수를 이용한 풀이이다.

 

다른 풀이

 DFS 방식으로 푸는 방법도 있습니다.

int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        stack<pair<TreeNode*, int>> s;
        s.push({root, 1});
        int len = 1;
        while (!s.empty()) {
            pair<TreeNode*, int> front = s.top(); s.pop();
            len = max(len, front.second);
            if (front.first->left) s.push({front.first->left, front.second+1});
            if (front.first->right) s.push({front.first->right, front.second+1});
        }
        return len;
}