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

문제 정책

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

예

 
  3
 / \
9   20
   /  \		 
  15   7

3

설명 : 아래 트리에서 빨간색으로 표시된 것과 같이 가능한 가장 긴 경로가 두 개 있습니다.

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)입니다.