Maximum Depth of Binary Tree(Tree,Depth-First Search,Breadth-First Search,Binary Tree)

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

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.

 

Example 1:

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

Example 2:

Input: root = [1,null,2]
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• -100 <= Node.val <= 100

요호~ 간만에 Tree문제다.

사실 BFT, DFT는 툭 치면 바로 탁 나올 정도로 익숙해져야 하기에 주기적으로 관련 문제를 풀어주는 것이 좋다.

 

각각의 경우 어떤 Container를 써야 하는지(Stack? Queue?) 어떤 알고리즘을 짜야 하는지가 좀 정해진듯한 느낌이 있어서 익숙해지는 것이 답이다.

 

1. Python

나름 Stack ( = 파이썬에서 deque) 을 써서 잘 풀었다고 생각하는데.. 왜 또 능률은 꽝으로 나오는지 -_- 알다가도 모르겄다.

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root : return 0
        ans = 1
        stack = deque([[root,1]])
        while stack:
            curr, cnt = stack.pop()
            if curr.left:
                stack.append([curr.left,cnt+1])
            if curr.right:
                stack.append([curr.right,cnt+1])
            ans = max(ans,cnt)
        return ans

 

나름 시간 효율 높힐려고 일반 list대신 deque까지 썼건만 -_- ㅎㅎ;;

 

 

2. C

보아하니, While문을 쓰지 않으면 Recursive로도 풀 수가 있다.

근데 나는 왜케 Recursive를 바로 떠올리기가 힘이 든 것일까 ㅠ

코드를 보면 Ah~ Moment는 있는데, 솔직히 첨부터 짜기가 넘 어렵다.

 

//  * Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}Tree;
 
int max(int a, int b){
    return a > b ? a : b;
}

int maxDepth(Tree* root) {
    if(!root) return 0;

    int left = maxDepth(root->left);
    int right = maxDepth(root->right);

    return 1 + max(left,right);

}

 

 

3. C++

이번엔 C++의 경우 반복적인 BFT를 사용해보겠다. 뭔가 간만에 Tree문제 만나서 신났다 ㅋ

이 Case는 GPT를 보고 얻은 아이디어긴 하다. 참.. 한 문제를 푸는데도 이렇게 많은 풀이가 존재하다닝

 

코딩의 영역은 끝이 없다!

 

#include <queue>
// using namespace std;
//  * 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) return 0;

        std::queue<TreeNode*> q;
        q.push(root);
        int ans = 0;

        while(!q.empty()){
            ans++;
            int n = q.size();
            for(int i=0;i<n;i++){
                TreeNode* curr = q.front();
                q.pop();
                if(curr->left) q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
        }
        return ans;
    }
};