数据库 主从复制 海思 swing ssh count configuration testng vue标签 linux源码在线阅读 matlab根号怎么打出来 java两个数组合并 java数据分析 matlab四舍五入 js字符串排序 java手机验证码 java获取字符串 range函数python python命令 python命令行参数 python指令 python正则匹配数字 java字符串 java时间 java游戏制作 网页游戏开发入门 修改mac地址软件 系统集成项目管理工程师教程 整站系统 msn格式 js刷新页面 汽车配件查询软件 微信公众号点餐系统 rpm卸载命令 卸载mysql 5s降级 ps怎么p人脸 ppt背景音乐怎么关 抖音道具 SQLite编辑器
当前位置: 首页 > 学习教程  > 编程语言

hazy’s leetcode刷题笔记(二)

2020/11/24 9:32:08 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

leetcode.222:完全二叉树的节点个数-每日一题 给出一个完全二叉树,求出该树的节点个数。 说明: 完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一…

leetcode.222:完全二叉树的节点个数-每日一题
给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/
2 3
/ \ /
4 5 6
输出: 6

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        /*
        来自评论区,相对于暴力递归更好的解法:
        完全二叉树的高度可以直接通过不断地访问左子树就可以获取
        判断左右子树的高度: 
        如果相等说明左子树是满二叉树, 然后进一步判断右子树的节点数(最后一层最后出现的节点必然在右子树中)
        如果不等说明右子树是深度小于左子树的满二叉树, 然后进一步判断左子树的节点数(最后一层最后出现的节点必然在左子树中)
        */
        if(root == null) return 0;
        //获得左右子树的深度
        int ld = getDepth(root.left);
        int rd = getDepth(root.right);
        // 1(根节点) + (1 << ld)-1(左完全左子树节点数) + 右子树节点数量
        if(ld == rd) return (1 << ld) + countNodes(root.right);
        // 1(根节点) + (1 << rd)-1(右完全右子树节点数) + 左子树节点数量
        else return(1 << rd) + countNodes(root.left);
 
    }
    //获得左右子树的深度
    private int getDepth(TreeNode root) {
        int dept = 0;
        while(root != null) {
            root = root.left;
            dept++;
        }
        return dept;
    }
}

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_400046.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?