이진 트리의 최대 깊이 찾기

Question

public class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    TreeNode(int x) { val = x; } 
} 

public class Solution { 
    public int maxDepth(TreeNode root) { 
     TreeNode focusNode = root; 
     TreeNode focusNode2 = root; 
     int count = 0; 
     int count1 = 0; 
     boolean a = true; 
     while (a) { 
      if (focusNode != null) { 
       count++; 
       focusNode = focusNode.left; 
      } 
      if (focusNode2 != null) { 
       count++; 
       focusNode2 = focusNode2.right; 
      } else { 
       a = false; 
      } 
     } 
     return Math.max(count,count1); 
    } 
} 

필자가 쓴이 코드가 예상되는 결과를 내지 못하는 이유가 혼란 스럽습니다. 그리고 나는 또한 최대 깊이의 정의와 혼동합니다. 오른쪽에있는 모든 노드 또는 왼쪽에 정렬 된 모든 노드를 고려하여 최대 깊이를 찾고 있습니까?

Answer 1

나는 나무의 높이 또는 노드의 깊이에 대해 이야기하고 있는지 확실하지 않습니다.
다음은 높이와 깊이의 정의입니다.

노드의 높이 - 노드의 높이는 노드와 리프 사이의 가장 긴 아래쪽 경로에있는 가장자리의 수입니다.

깊이 - 노드의 깊이는 노드에서 트리의 루트 노드까지의 가장자리 수입니다. 예를 들어

   R 
      /\ 
       A B 
      /\/\ 
      C D E F 
       \ 
       G  

:
노드 R의 깊이는 0이고 높이가 3
노드 G의 깊이가 3이고 높이가 0

하자 당신이 나무의 높이를 찾는 가정이다.
왜 프로그램이 원하는 결과를 얻을 수 없습니까?
코드가

하자가 예로서 그림에서 나무를 사용하여 나무 내부의 모든 노드를 통과하지 않았기 때문에 그것은이다 : 루프에서
를 처음 focusNode, focusNode2 = 노드 R

focusNode R>을 드릴 것입니다 A> C
focusNode2 R> B> F> 종료

트리 중간에있는 모든 하위 노드는 계산되지 않았습니다. 트리가 완벽한 이진 트리가 아니면 잘못된 대답을 얻습니다.

은 예약 주문 Travesal이
https://en.wikipedia.org/wiki/Tree_traversal

Answer 2

당신은 전체 트리를 통과하지 않는 같은 트리를 탐색하는 방법에 대한 몇 가지 알고리즘을 읽을 수 있습니다 것이 좋습니다. 맨 왼쪽과 맨 오른쪽 경로 만 실행 중입니다.

일반적으로 재귀는 모든 노드를 간단하고 고립되어 처리 할 수 ​​있으므로 이진 트리가있는 친구입니다.

는 이러한 사실을 이용하게 노드 클래스의 depth() 방법 정의 :

• 널 아이의 깊이가 제로
• null이 아닌 아이의 깊이가 호출에 의해 발견되어 그 depth() 방법 (즉, 재귀 적으로)
• 이 this 노드의 깊이가 그 아이의 깊이의 최대이다, 플러스 1 (그래서 그 자체를 계산)

이를 구현하고 루트 노드에서 depth()을 호출하여 트리의 최대 깊이를 찾습니다. 해당 구현의 재귀 적 특성은 전체 트리를 통과합니다.