当前位置：首页 > news >正文

Leetcode Hot 100 | 543.二叉树的直径 | 递归+优化

news 来源：原创 2024/10/1 17:54:25

写法一

自己一开始直接写的，没考虑时间复杂度…

class Solution {/*递归思路：不准进递归（除非之后用简单例子验证一下）将方法按照自己想要返回的值来补充其他的代码细节；用最值来模拟返回结果+补充代码细节（最高和最低）；再用简单例子走一遍全过程修改代码*///计算对当前结点来说的最大直径 【递归调用】public int diameterOfBinaryTree(TreeNode root) {//【边界用最低来模拟】if(root == null)return 0;//【用最高来模拟】//算当前结点的最大直径int res1 = maxHeight(root.left)+maxHeight(root.right);//算当前结点的左子结点的最大直径int res2 = diameterOfBinaryTree(root.left);//算当前结点的右子结点的最大直径int res3 = diameterOfBinaryTree(root.right);//三个值里面取最大值int res4 = Math.max(res1,res2);int res = Math.max(res3,res4);//返回直径最大值return res;}// 计算当前结点到其左结点（或右结点）最底端的最长高度 (经过的枝) 【递归调用】// 【其实准确计算的是当前结点到其左结点（或右结点）最底端经过的最多的结点 【只不过结点比树枝少1 (2结点=1树枝) ；（刚好在调用处就不用再+1了(即不用算连接根的那个枝了)）】】public int maxHeight(TreeNode node){//【边界用最低来模拟】if(node == null)return 0;//【用最高来模拟】int res1 = maxHeight(node.left);int res2 = maxHeight(node.right);return Math.max(res1,res2)+1;}
}

时间和内存：
在这里插入图片描述

写法二：优化了下

class Solution {public int res = 0;public int diameterOfBinaryTree(TreeNode root) {/*** 和法一写的区别：*  1.该函数只负责调用不负责返回值；方法一函数负责返回值，在调用处才计算 【能在函数内实现就在函数内实现，简单高效快捷美观】*  2.该函数传入的是root，直接内部递归计算左右结点了(不用返回root值，最多就返回到root的左右子结点，刚好能计算以root为根的直径)；方法一传入的是左右结点，而且还递归传入...【这个方法的优化高效省内存节省时间】*  3.该方法的res是全局变量，递归一次就能计算好(边递归边计算的)；方法一的res是全部递归之后才算的，每次都递归root和左右根的计算...【太耗了，这个的一次递归计算更方便！】*///传root进去，只是递归计算其所有左结点（右结点）数量【即以root为根的树杈】culculateDiameter(root);return res;}/*(假设左边有三道左结点)当前结点返回给上一层结点包括当前结点在内的所有子结点的个数 = 当前的层数 = 对上一层结点来说接收的就是以上一层结点为根的所有树杈数量即：结点数 = 层数 = 杈数+1 ； 深度 = 层数 ， 长度 = 杈数*///这里最多用到root的左右子结点的返回值返回完就结束了，最后一次返回值给调用处的root没用，所以虽然计算的是结点数，但用到的还是结点数-1=树杈数public int culculateDiameter(TreeNode node){if(node == null) return 0;int l = culculateDiameter(node.left);int r = culculateDiameter(node.right);res = Math.max(res,l+r);return Math.max(l,r)+1;}}