LeetCode 두 갈래 나무 최대 최소 깊이

6423 단어 문제를 풀다

두 갈래 나무 최대 깊이


좌우 자목으로 돌아가 비교적 큰 깊이를 되돌려주고 끝 조건은 잎 노드를 두루 돌아다니는 좌우 아이가 비어 0을 되돌려주는 것이다.마지막으로 루트 노드의 값을 추가합니다.
leetcode 104
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))

두 갈래 나무의 최소 깊이


귀속, 잎 노드 0 반환;
주의: 최소 깊이는 뿌리 노드에서 잎 노드까지의 최소 경로 길이를 정의하기 때문에 최대 깊이의 코드를 min에서 max로 바꾸면 되지 않습니다.
루트 노드의 좌우 하위 트리가 비어 있으면 비어 있는 이 경로는 계속 갈 수 없습니다. 따라서 최소 경로는 비어 있지 않은 경로의 길이에 현재 노드의 1을 더해야 합니다.
왼쪽 트리가 비어 있으면 1 + 오른쪽 트리 깊이를 반환합니다.이때 뿌리 노드 a와 오른쪽 나무 b만 있고 이때 최소 깊이는 2이라고 상상할 수 있다.좌우 나무가 비어 있지 않으면 1+좌우 나무 중 가장 작은 깊이를 되돌려줍니다.
leetcode 111
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        elif root.left == None:
            return 1 + self.minDepth(root.right)
        elif root.right == None:
            return 1 + self.minDepth(root.left)
        else:
            return 1 + min (self.minDepth(root.right),self.minDepth(root.left))

N 포크 트리 최대 깊이


원리는 두 갈래 나무와 비슷하여 모든 하위 노드를 훑어보는 leetcode 559로 바뀌었다
class Solution:
    def maxDepth(self, root: 'Node') -> 'int':
        if not root:
            return 0
        max_depth_child = 0
        for child in root.children:
            curr_depth = self.maxDepth(child)
            if curr_depth > max_depth_child:
                max_depth_child = curr_depth
        return 1 + max_depth_child

좋은 웹페이지 즐겨찾기