leetcode543. Diameter of Binary Tree

제목 요구
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example: Given a binary tree
      1
     / \
    2   3
   / \   
  4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
이 진 트 리 의 지름 은 한 잎 노드 에서 다른 잎 노드 까지 의 가장 먼 거 리 를 말 하 는데 이 거 리 는 두 노드 간 의 경로 가 길 다 는 것 을 말 하 는데 이 경 로 는 반드시 뿌리 노드 를 거치 지 않 는 다 는 것 을 주의해 야 한다.
아이디어 와 코드
여기 서 재 귀 를 통 해 계산 을 완성 할 수 있 습 니 다. 먼저 재 귀 를 통 해 왼쪽 서브 트 리 의 최대 높이 를 계산 한 다음 에 재 귀 를 통 해 오른쪽 서브 트 리 의 최대 높이 를 계산 하면 현재 노드 가 구성 할 수 있 는 가장 긴 경 로 를 얻 을 수 있 습 니 다.이 값 을 기록 해 야 합 니 다.재 귀적 으로 이 노드 의 최대 높이 를 외부 호출 자 에 게 운송 합 니 다.
int max = 0;  
public int diameterOfBinaryTree(TreeNode root) {  
    heightOfBinaryTree(root);  
    return max;  
}  
  
public int heightOfBinaryTree(TreeNode root) {  
    if (root == null) {  
        return 0;  
    }  
    int left = heightOfBinaryTree(root.left);  
    int right = heightOfBinaryTree(root.right);  
    max = Math.max(left + right + 1, max);  
    return Math.max(left, right) + 1;  
}

좋은 웹페이지 즐겨찾기