Leetcode 104: 두 갈래 나무의 최대 깊이(가장 자세한 해법!!!)

두 갈래 나무를 정해 최대 깊이를 찾아라.
두 갈래 나무의 깊이는 뿌리 노드에서 가장 먼 잎 노드까지의 가장 긴 경로의 노드 수이다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 포크 트리 지정[3,9,20,null,null,15,7],

최대 깊이 3을 반환합니다.
문제 풀이 사고방식
전체 문제의 간단한 사고방식은 바로 사용의 귀속이다.어떻게 하지?우리는 maxDepth를 통해 각각 왼쪽 나무와 오른쪽 나무의 깊이를 계산하고 이 두 깊이를 비교하여 최대치k를 얻는다.그러면 현재 이 나무의 깊이의 최대치는 k + 1 이 된다.So easy!!O(∩_∩)O

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0

        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

물론 저희가 더 간결하게 쓸 수 있어요.

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

그러나 아직 끝나지 않았다. 귀속으로 해결할 수 있는 문제에 대해 우리는 어떻게 교체를 통해 해결할 수 있는지 생각해야 한다.그럼 이 문제는 어떻게 교체를 통해 해결합니까?그러면 우리는 stack 을 사용하여 stack 위의 귀속 과정을 시뮬레이션할 것이다.비교적 간단한 사고방식은 바로 두 갈래 나무의 층차 역력이다. 이 Leetcode 102: 두 갈래 나무의 층차 역력(가장 상세한 해결 방안!!!)을 참고하면우리는 이 기초 위에서 조금만 수정하면 된다.

class Solution:
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        q = [(root, 1)]
        result = 0
        while q:
            node, depth = q.pop(0)
            if node:
                result = max(result, depth)
                q.extend([(node.left, depth + 1), (node.right, depth + 1)])
                
        return result

하나pythonic의 작법

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        q = [(root, 0)]
        while q:
            node, depth = q.pop(0)
            if node:
                q.extend([(node.left, depth + 1), (node.right, depth + 1)])
        else:
            return depth

이 질문의 다른 언어 버전을 GitHub Leetcode에 추가했습니다.
문제가 있으면 여러분이 지적해 주시기 바랍니다!!!

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Leetcode 199: 두 갈래 나무의 오른쪽 보기(초상세 해법!!!)

두 갈래 나무를 정해서 오른쪽에 서 있는 것을 상상하고 꼭대기에서 끝까지 순서대로 오른쪽에서 볼 수 있는 노드 값을 되돌려줍니다. 예: 문제 풀이 사고방식 이 문제는 사실 Leetcode 102: 두 갈래 나무의 차...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Leetcode 104: 두 갈래 나무의 최대 깊이(가장 자세한 해법!!!)

좋은 웹페이지 즐겨찾기