Diameter of Binary Tree

发布时间：2020-12-14 04:46:48 所属栏目：大数据来源：网络整理

导读：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

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,3].

Note:?The length of path between two nodes is represented by the number of edges between them.

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 class Solution {
11     public int diameterOfBinaryTree(TreeNode root) {
12         int[] globalMax = new int[1];
13         helper(root,globalMax);
14         return globalMax[0] - 1 <= 0 ? 0 : globalMax[0] - 1;
15     }
16     
17     private int helper(TreeNode root,int[] globalMax) {
18         if (root == null) return 0;
19         int leftMaxWithRoot = helper(root.left,globalMax);
20         int leftRightWithRoot = helper(root.right,globalMax);
21         
22         int maxWithRoot = Math.max(leftMaxWithRoot,leftRightWithRoot) + 1;
23         globalMax[0] = Math.max(globalMax[0],leftMaxWithRoot + leftRightWithRoot + 1);
24         return maxWithRoot;
25     }
26 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!