LeetCode 543. Diameter of Binary Tree
原创LeetCode 543. Diameter of Binary Tree
原创
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 the longestpath 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.
题目大意：求一个二叉树中的任意两个节点的最长路径
解法一：
直接但是效率地下的解法，我们首先写一个求二叉树深度的函数depthTree(),求出二叉树的左右深度，依次遍历整个二叉树，就可以求出最大的深度。
public int diameterOfBinaryTree(TreeNode root) {
if (root==null) return 0;
return Math.max(depthTree(root.left)+depthTree(root.right),Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right)));
}
public int depthTree(TreeNode root){
if (root == null) return 0;
return 1+Math.max(depthTree(root.right),depthTree(root.left));
}解法二：
这个递归的设计是从下往上遍历二叉树的。left代表沿着root的左孩子的方向的深度，right代表沿着root的右孩子的方向的深度，二者相加就是顶点为root的一条最大路径。
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
getDiameter(root);
return max;
}
public int getDiameter(TreeNode root) {
if (root == null) return 0;
int left = getDiameter(root.left);
int right = getDiameter(root.right);
max = Math.max(max, left+right);
return Math.max(left, right) + 1;
}
}下面将getDiameter()函数加两个输出：
public int getDiamter(TreeNode root){
if (root == null) return 0;
int left = getDiamter(root.left);
System.out.println(left);
int right = getDiamter(root.right);
System.out.println(right);
max = Math.max(max,left+right);
return Math.max(left,right)+1;
}对于一个输入：
5
// / \
// 3 6
// / \
// 2 4
/
1 输出为：
0
0
1
0
2
0
0
1
3
0
0
1
4示例：
5
/ \
3 6
/ \
2 4
/ \
1 null
/ \
null null 0 0 1 0 2 0 0 1 3 0 0 1 4这样可以很清楚的看到递归的过程。
不使用全局遍历的写法：
public int diameterOfBinaryTree(TreeNode root) {
int[] res = new int[1];
getDiamter(root,res);
return res[0];
}
public int getDiamter(TreeNode root,int[] res){
if (root == null) return 0;
int left = getDiamter(root.left,res);
int right = getDiamter(root.right,res);
res[0] = Math.max(res[0],left+right);
return Math.max(left,right)+1;
}总结：对与二叉树的递归形式有很多，合适的递归方式可以有效的简化算法的复杂度。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。