- 递归
函数为:
public int diameterOfBinaryTree(TreeNode root)
我的思考过程:
- 最大直径表示的是两节点之间的边的数目,考虑左右子树的最大直径,如下:
int left_length = diameterOfBinaryTree(root.left); int right_length = diameterOfBinaryTree(root.right);
可以得到左子树的最大直径left_depth,右子树的最大直径right_depth。
- 除此之外,还有一种可能没有考虑就是最大直径经过根节点,此时的边的个数等于左右子树深度相加。
- 最终完整树的最大直径就是左子树最大直径,右子树最大直径和经过根节点最大直径的三种情形的最大值。
具体代码如下:
class Solution { //最大值 int max(int m,int n){ if(m > n) return m; else return n; } //树的深度 public int TreeDepth(TreeNode root){ if(root == null) return 0; int m = TreeDepth(root.left); int n = TreeDepth(root.right); return max(m,n)+1; } public int diameterOfBinaryTree(TreeNode root) { if(root == null) return 0; int left = TreeDepth(root.left);//左子树的深度 int right = TreeDepth(root.right);//右子树的深度 int left_length = diameterOfBinaryTree(root.left);//左子树最大直径 int right_length = diameterOfBinaryTree(root.right);//右子树最大直径 int maxDiameterOfSubTree = max(left_length,right_length); return max(maxDiameterOfSubTree,(left+right)); } }
- 官方解答
class Solution { int ans = 0; public int diameterOfBinaryTree(TreeNode root) { TreeDepth(root); return ans; } public int TreeDepth(TreeNode root){ if(root == null) return 0; int m = TreeDepth(root.left); int n = TreeDepth(root.right); ans = Math.max(ans,m+n);//递归所有节点的同时,将最大值记录下来 return Math.max(m,n)+1; } }
官方解答的时间的复杂度O(n),我的方法写麻烦了。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)