두 갈래 나무의 최대 지름

1292 단어 leetCode
543. 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 thelongest 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.
두 갈래 나무의 지름: 두 갈래 나무 중 한 결점에서 다른 노드로 가는 가장 긴 경로, 두 갈래 나무의 지름은 분리와 귀속의 사상을 채택한다. 뿌리 노드가 루트인 두 갈래 나무의 지름=Max(왼쪽 나무의 지름, 오른쪽 나무의 지름, 왼쪽 나무의 최대 깊이(뿌리 노드를 포함하지 않음) + 오른쪽 나무의 최대 깊이(뿌리 노드를 포함하지 않음) +1)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 
	//  , 
	int diameter = 0;
 
	public int diameterOfBinaryTree(TreeNode root) {
		getDepth(root);
		return diameter;
	}
 
	//  
	private int getDepth(TreeNode root) {
		if (root == null)
			return 0;
		int l = getDepth(root.left);
		int r = getDepth(root.right);
		diameter = Math.max(diameter, l + r);
		return Math.max(l, r) + 1;
	}
}

좋은 웹페이지 즐겨찾기