[LeetCode] Maximum Depth of Binary Tree (feat. 고정관념?)

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

Maximum Depth of Binary Tree - LeetCode

바로 전 문제와 반대로 가장 깊은 leaf node의 depth를 구하는 문제이다. 간단한 DFS 문제이고, 재귀를 이용해 풀었다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        if(root->left==nullptr && root->right==nullptr)
            return 1;
        else if(root->left==nullptr)
            return maxDepth(root->right)+1;
        else if(root->right==nullptr)
            return maxDepth(root->left)+1;
        else {
            int left = maxDepth(root->left);
            int right = maxDepth(root->right);
            return (left > right ? left+1 : right+1);
        }
    }
};

 

다만 흥미로웠던 점이 있었다. 로직이 간단하기에 여러 언어로 변환하여 제출해봤는데, 의외로 Java가 가장 빨랐다.
모두 재귀를 이용한 DFS라는 같은 로직이었는데, Java > C >> C++ >> C# 순이었다. C#이 느린거야 예상했던 것이지만, Java가 C보다 빠를 줄은 몰랐고, C와 C++의 속도 차이도 꽤 났다. 다만 메모리 차이는 생각대로였다.

생각과 달라서 찾아봤지만 뚜렷한 해답은 찾지 못했고, 다만 재귀에서 함수(메서드) 호출 시 Java는 최적화가 되었고 C/C++은 재귀 횟수에 비례하여 시간이 늘었다는 글을 보았다. 하지만 정확한 근거가 있는 말이 아니어서 아직 제대로 원인을 알지 못했다.

원래 Java가 느리다는게 편견인지..? Java와 C#은 IL(중간 언어)를 거치기에 C/C++에 비해 상대적으로 느리다고 알고 있었는데 말이다.

기회가 되면 한 번 찾아봐야겠다. 혹시 알 것 같은 분들은 이 글을 보신다면 댓글로 달아주시면 감사하겠습니다!