이진 트리 Leetcode 솔루션의 최대 깊이

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Facebook Microsoft
알고리즘 이진 트리 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 재귀 트리 순회조회수 37

문제 정책

문제에서 이진 트리 주어진 나무의 최대 깊이를 찾아야합니다. 이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가장 긴 경로를 따라있는 노드 수입니다.

 
  3
 / \
9   20
   /  \		 
  15   7
3

설명 : 아래 트리에서 빨간색으로 표시된 것과 같이 가능한 가장 긴 경로가 두 개 있습니다.
이진 트리 Leetcode 솔루션의 최대 깊이

Empty Tree
0

나무가 비어 있으므로 깊이는 0입니다.

0
1

노드가 하나뿐이므로 깊이는 1입니다.

접근

트리의 최대 깊이를 찾기 위해 간단한 재귀 접근 방식을 적용 할 수 있습니다. 각 함수 호출은 'root'라는 루트 노드가있는 하위 트리를 나타냅니다. 루트 노드에서 시작하는 재귀 함수로 트리를 순회합니다.

따라서 기본 케이스는 하위 트리가 비어있는 경우입니다. 즉 루트가 NULL입니다. 그래서 우리는 깊이를 0으로 반환합니다.

루트가 NULL이 아니면 왼쪽 자식과 오른쪽 자식에 대해 동일한 함수를 재귀 적으로 호출합니다.

그림과 같이 두 개의 자식 함수가 깊이를 반환 할 때이 두 하위 트리에서 최대 값을 선택하고 여기에 1을 더한 후이 값을 반환합니다 (두 하위 트리의 부모 인 현재 노드 추가).

이진 트리의 최대 깊이

실시

이진 트리 Leetcode 솔루션의 최대 깊이를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
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) {}
};

int maxDepth(TreeNode* root) 
{
    if(root==NULL) return 0;
    return 1+max(maxDepth(root->left),maxDepth(root->right));
}

int main() 
{
    TreeNode *root= new TreeNode(3);
    root->left= new TreeNode(9);
    root->right= new TreeNode(20);
    root->right->left= new TreeNode(15);
    root->right->right= new TreeNode(7);
    
    cout<<maxDepth(root)<<endl; 
  return 0; 
}
3

이진 트리 Leetcode 솔루션의 최대 깊이를위한 Java 프로그램

import java.util.*;
import java.lang.*;
class TreeNode 
{
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) 
      {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class MaxDepth
{  
    public static int maxDepth(TreeNode root) 
    {
        if(root==null) return 0;
        
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
    
    public static void main(String args[])
    {
        TreeNode root= new TreeNode(3);
        root.left= new TreeNode(9);
        root.right= new TreeNode(20);
        root.right.left= new TreeNode(15);
        root.right.right= new TreeNode(7);
       
        System.out.println(maxDepth(root));
        
    }
}
3

이진 트리 Leetcode 솔루션의 최대 깊이를위한 복잡성 분석

시간 복잡성

의 위에) :  각 노드를 정확히 한 번 방문하므로 시간 복잡도는 O (N)이며, 여기서 N은 주어진 트리의 총 노드 수입니다.

공간 복잡성 

의 위에) :  최악의 경우 트리는 완전히 불균형입니다. 예를 들어 각 노드에는 왼쪽 자식 노드 만 있거나 오른쪽 자식 노드 만 있으면 재귀 호출이 N 번 발생합니다 (트리의 높이). 따라서 호출 스택의 최대 크기는 O (N)입니다.
최상의 경우 (나무가 완전히 균형을 이룬 경우) 나무의 높이는 log⁡ (N)이됩니다. 따라서이 경우 공간 복잡도는 O (log⁡ (N)입니다.

코멘트를 남겨

Translate »
1