[1] 104. Maximum Depth of Binary Tree

[robert-min]

문제 추천 이유!!

• 트리노드의 개념 복습 필요
• 오랜만에 풀었을 때, 당황

문제 링크

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

*작성가이드 입니다.

1. 작성자가 먼저 문제를 풀어봅니다.
2. 문제를 풀고나서 난이도를 설정합니다.
   • 1 : 30분 이내로 손 쉽게 풀 수 있음
   • 2 : 1시간 이내로 고민하면 풀 수 있음
   • 3 : 1시간 이상 걸리거나 어려움
3. Coding test Basic template을 사용하여 이슈를 생성합니다.
   • 제목은 : [난이도] 문제명으로 작성합니다.
   • 내용은 : 문제 링크만 추가하세요
   • 문제 사이트를 label로 추가해주세요. 기본값은 백준
4. 문제 풀이는 이슈의 코멘트로 추가해주세요
   • 풀이에 걸린 시간, 풀이 유형, 방식은 간단하게
   • 문제를 풀고나서 스스로 풀이 또는 오답노트를 정리하는 느낌으로!!
5. 다른 사람에게 채팅으로 직접 문제를 추천하세요.
   • 디스코드 채널을 통해 다른 모임원에게 문제를 추천
   • 해당 모임원은 문제를 풀고 코멘트를 통해 추가로 공유하기!!

---

아래는 comment 템플릿입니다.(복사해서 사용)

⏰ 소요 시간 : 
🗂️ 유형 :

🖌️ 문제 풀이
- 

[robert-min]

⏰ 소요 시간 : X 🗂️ 유형 : DFS

🖌️ 문제 풀이

• 오랜만에 풀어서 헷갈린 건지, leetcode에서 root = [....]이 tree node 형태로 되어있음(리스트로 생각해서 노드부터 만들어야하는거라 생각했더니 문제가 복잡해짐)
• DFS를 사용해서 depth 계산

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

• stack 풀이

  class Solution:
  def maxDepth(self, root: Optional[TreeNode]) -> int:
      if not root:
          return 0
      max_depth = 0
      stack = [(root, 1)]
      while stack:
          node, depth = stack.pop()
          max_depth = max(depth, max_depth)
          if node.left:
              stack.append((node.left, depth + 1))
          if node.right:
              stack.append((node.right, depth + 1))
      return max_depth

[robert-min]

유사한 문제 : 872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/?envType=study-plan-v2&envId=leetcode-75

• dfs 풀이

  class Solution(object):
  def leafSimilar(self, root1, root2):
  
      def dfs(node, leaf_sequence):
          if not node:
              return
          if not node.left and not node.right:  # Leaf node
              leaf_sequence.append(node.val)
          dfs(node.left, leaf_sequence)
          dfs(node.right, leaf_sequence)
  
      leaf_sequence1 = []
      leaf_sequence2 = []
      dfs(root1, leaf_sequence1)
      dfs(root2, leaf_sequence2)
  
      return leaf_sequence1 == leaf_sequence2

• stack 풀이

class Solution(object):

    def find_leaf(self, root):
        leaf = []
        stack = [root]
        while stack:
            now = stack.pop()
            if not now.left and not now.right:
                leaf.append(now.val)
            else:
                if now.left:
                    stack.append(now.left)
                if now.right:
                    stack.append(now.right)
        return leaf

    def leafSimilar(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        result1 = self.find_leaf(root1)
        result2 = self.find_leaf(root2)
        if result1 == result2:
            return True
        else:
            return False