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

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

article 2024/10/1 10:00:30

写法一

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

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;
    }

}