이진 트리의 깊이를 계산하는 방법을 이해하십시오

Question

커리어 컵 가이드를 통해 기본 CS 원칙을 통해 충돌 과정을 진행하고 이진 트리의 최소/최대 깊이를 계산하는 예제를 고수합니다. 이것이 내가 거의 모든 예제를 가지고있는 것과 같은 문제이기 때문에 나는 여기에 질문을 게시 할 것이라고 생각했다.

지침은 트리가 균형을 이루고 있는지 확인하는 방법을 구현하는 것입니다. 이를 수행하려면 최소 깊이와 최대 깊이를 비교하여 그 차이가 1보다 크지 않은지 확인해야합니다.이 원리는 이해하는 것처럼 간단합니다. 15 행의 메소드는이를 수행하기위한 것입니다.

그러나 각 도우미 메서드 (maxDepth 및 minDepth)의 return 문에서 무슨 일이 일어나고 있는지 이해할 수 없습니다. 숫자는 root.left 또는 root.right에서 어떻게 파생됩니까? 는 Math.max 기능은 단순히 값을 (단지 Node Object)를 지정하지되고있다 때문에 1 또는 0이 값/널 노드가, 또는 가정 하는가 따라서 1하여 리턴 값까지를 증가시키는 Math.max(maxDepth(root.left), maxDepth(root.right) 자체 동일 0 수행 두 노드 모두 null입니까?

는 = 루트는 자녀가 않습니다 minDepth :

그렇다면이 나무의 최소/최대 깊이를 계산하는 데 사용되는 일반적인 과정이다? 예 = minDepth = 1, no = minDepth = 0 (루트가있는 경우)

maxDepth = 루트에서 리프를 가장 멀리 찾을 때까지 두 분기를 순환합니다. 카운터를 유지하여 나뭇잎을 결정하십시오.

1 public static int maxDepth(TreeNode root) { 
2  if (root == null) { 
3  return 0; 
4  } 
5  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); 
6 } 
7 
8 public static int minDepth(TreeNode root) { 
9  if (root == null) { 
10   return 0; 
11  } 
12  return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
13 } 
14 
15 public static boolean isBalanced(TreeNode root){ 
16  return (maxDepth(root) - minDepth(root) <= 1); 
17 } 

Answer 1

maxDepth(root.left) 왼쪽 하위 트리의 최대 깊이를 반환합니다.
maxDepth(root.right)은 오른쪽 하위 트리의 최대 깊이를 반환합니다.
이 두 개의 최대 값은 최대 서브 트리 깊이입니다.
루트 노드에 1을 더하면 트리의 최대 깊이를 얻습니다.

이 트리입니다 가정 :

  A 
     B  C 
     D E F G 
    H 
    I 

그냥보고 당신은 최대 깊이는 5, 3 (여러 경로에 의해 형성되며, 최소 깊이 (경로 ABDHI에 의해 형성)되어 볼 수 있습니다 ACG 예제).

이제 최대 깊이는 1 (루트 A의 경우) + 2 개의 하위 트리의 최대 깊이입니다.
루트가 B 인 첫 번째 하위 트리의 최대 깊이는 4입니다 (B-D-H-I). 루트가 C 인 두 번째 하위 트리의 최대 깊이는 2입니다 (C-F). 우리가 서브를 표현하기 위해 내 샘플 트리에 문자를 사용하는 경우
최대 (4,2) = 4
따라서 전체 트리의 최대 깊이는 1 개 + 최대 (4,2) = 5

입니다 이러한 노드에 뿌리를 둔 나무, 우리는 얻을 :

maxDepth(A) = 1 + max(maxDepth(B) , maxDepth(C)) = 
       1 + max(1 + max(maxDepth(D) , maxDepth(E)), 1 + max(maxDepth(F) , maxDepth(G)) = 
       1 + max(1 + max(1+max(maxDepth(H),0) , 1+max(0,0)), 1 + max(1+max(0,0) , 1+max(0,0)) = 
       1 + max(1 + max(1+max(1+max(maxDepth(I),0),0) , 1), 1 + 1) = 
       1 + max(1 + max(1+max(1+max(1+max(0,0),0),0) , 1), 1 + 1) = 
       1 + max(1 + max(1+max(1+max(1,0),0) , 1), 2) = 
       1 + max(1 + max(1+max(2,0) , 1), 2) = 
       1 + max(1 + max(3 , 1), 2) = 
       1 + max(4, 2) = 
       1 + 4 = 
       5 

마찬가지로, 최소 깊이를 계산하기 위해, 당신은 두 가지의 최소를 가지고 가고, 추가 (왼쪽 및 오른쪽)이 하위 트리의 최소 깊이를 계산 1은 루트입니다.

Answer 2

글쎄, 나무의 양면을 확인한 다음 결과를 최대 또는 최소와 비교하는 재귀 함수입니다.

그림 도움.

 o go left and right 
    / \ 
(+1)o  o(+1)  
    \  
    o(+1) 

코드로 다시 가져올 수 있습니다.

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

호출 스택은 기본적으로이

// max return 2 
- left +1      
    // max return 1 
    -left 0      
    -right +1 
     // max return 0 
     -left 0     
     -right 0 
- right +1 
    //max return 0 
    -left 0 
    -right 0 

Min 작품 같은 방법처럼 보일 것입니다.