`

Count Complete Tree Nodes

阅读更多
Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

给定一个完全二叉树,让我们输出二叉树中节点的个数。我们知道一个满二叉树的节点个数是2^k - 1 (k 为二叉树的高度), 我们设定两个标志left 和right,代表当前节点的左侧和右侧的高度是否被计算过,它们通过left和right的值来判断当前子树是否为满二叉树,因为如果为满二叉树,我们就可以用公式计算出它的节点个数,如果left和right的值不相等,我们就递归循环这个过程。代码如下:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        return getCount(root, 0, 0);
    }
    public int getCount(TreeNode root, int lCount, int rCount) {
        if(lCount == 0) {
            lCount = 0;
            TreeNode cur = root;
            while(cur != null) {
                lCount ++;
                cur = cur.left;
            }
        }
        if(rCount == 0) {
            rCount = 0;
            TreeNode cur = root;
            while(cur != null) {
                rCount ++;
                cur = cur.right;
            }
        }
        if(lCount == rCount) return (1 << lCount) - 1;
        return 1 + getCount(root.left, lCount - 1, 0) + getCount(root.right, 0, rCount - 1);
    }
}
1
1
分享到:
评论

相关推荐

    java-leetcode题解之Count Complete Tree Nodes.java

    java java_leetcode题解之Count Complete Tree Nodes.java

    leetcodetreenode-count-complete-tree-nodes:计算完整二叉树中的总节点数

    tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int totalNodes = 0 ; public int countNodes ( TreeNode root ) {...

    多级数据-Mysql中的递归层次查询(父子查询).doc

    首先,我们需要创建一个名为 `treenodes` 的表来存储节点信息,包括节点 ID、节点名称和父节点 ID。 ```sql CREATE TABLE `treenodes` ( `id` int(11) NOT NULL, `nodename` varchar(20) DEFAULT NULL, `pid` ...

    count-leaf-nodes.rar_count leaf_countleaf

    这个"count-leaf-nodes.rar_count leaf_countleaf"的压缩包文件显然涉及到与树相关的两个操作:计算叶子节点的数量以及交换二叉树的左右子树。 首先,让我们详细探讨如何**计算叶子节点**(也称为终端节点)的数量...

    TestTreeWebApi:#C##ASP.NET Core#实体框架

    GET /TreeNodes返回所有TreeNodes GET /TreeNodes/{id} -返回具有指定ID的TreeNode GET /TreeNodes/by-name/{name} -返回具有指定名称的TreeNode PUT /TreeNodes/{name}/update-name [body { newName: "string"}]...

    陈越、何钦铭-数据结构作业16:Complete Binary Search Tree完全二叉搜索树

    A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Now given a sequence of distinct non-negative ...

    tree节点移动 Tree节点移动到DataGrid Winfrom 皮肤

    在Windows Forms(WinForms)应用开发中,我们经常会遇到数据展示和操作的需求,例如将`TreeNodes`(树形结构的节点)与`DataGrids`(数据网格)结合使用。`TreeNode`是`TreeView`控件的基本元素,用于表示层次化的...

    ILSpy:icsharpcode/ILSpy

    反编译为 C#(查看语言支持状态)) 整个项目反编译 搜索类型/方法/属性(了解选项) 基于超链接的类型/方法/属性导航 基本/派生类型导航、历史记录 程序集元数据资源管理器(功能演练)) BAML 到 XAML 反编译器 ...

    count_struct_nodes(​a_struct):计算结构中的元素数量-matlab开发

    `count_struct_nodes(a_struct)`函数就是用于解决这个问题的,它能帮助我们计算一个结构体中所有非结构子元素的总数。 首先,让我们深入了解结构体的概念。在MATLAB中,结构体由一组字段(field)组成,每个字段都...

    jsTree中文文档

    var selected_nodes = $('#jstree_demo_div').jstree('get_selected'); ``` **插件扩展** jsTree 具有一系列内置插件,如 `'checkbox'` 插件,用于实现多选功能;`'dnd'` 插件,用于拖放操作;`'search'` 插件,...

    基础算法-Python遍历打印二叉树

    /usr/bin/pythonclass TreeNode(): def __init__(self, val): self.val = val self.left = None self.right = Nonedef list_create_tree(root_node, tree_nodes_val, i): if i (tree_nodes_val): if tree_nodes_val...

    jsTree动态tree

    **jsTree动态tree详解** jsTree是一款基于JavaScript的开源库,专门用于构建交互式的树形视图。在网页开发中,树形结构常用于展示层级关系的数据,如目录、组织结构或导航菜单等。jsTree提供了丰富的API和可定制的...

    alvtree完全展开合并讲解.docx

    在 SAP 系统中,ALVTREE 是一种用于展示层级数据的控件,它与标准的 TREE 控件有所不同。在标准的 ALVTREE 实现中,并没有提供预置的完全展开和完全合并的功能,因此在实际应用中,我们需要通过自定义的方式来实现...

    kad协议里的nodes.dat文件抓包详解

    nodes.dat文件是kad网络中存储节点信息的数据文件,它包含了一系列节点的标识符(ID)和它们的网络地址(IP地址和端口号)。在本篇详解中,我们将深入探讨如何对kad协议中的nodes.dat文件进行抓包分析,以及从这些...

    Easyui tree 测试demo

    从 tree2_demo.html 中我们可以学习到 Tree 的基本结构和配置,从 tree2_getdata.php 和 conn.php 学习到数据获取和处理的方法,而 nodes.sql 则帮助我们理解数据存储和组织的方式。对于想要学习和使用 EasyUI Tree ...

    jsTree实例,jsTree实例

    1. **节点 (Nodes)**:jsTree 中的基本元素,可以是树的根节点或子节点。每个节点包含文本、ID、图标等属性,并可拥有子节点。 2. **容器 (Container)**:通常是一个 HTML 元素,如 `div`,用于承载整个树结构。 3...

    jstree树形菜单结构 树形菜单结构.zip

    return Json(treeNodes, JsonRequestBehavior.AllowGet); } ``` 这里,`YourTreeNodeModel`是你自定义的节点模型,包含文本、ID和其他可能的属性。 至于压缩包中的文件`www.zzx8.com`和`H`,它们似乎并不是jstree...

    java-leetcode题解之All Nodes Distance K in Binary Tree.java

    java基础 java_leetcode题解之All Nodes Distance K in Binary Tree.java

    mysql递归调用获取树节点(子树).pdf

    select tmpLst.*,treeNodes.* from tmpLst,treeNodes where tmpLst.id=treeNodes.id order by tmpLst.sno; END ``` 2. `createChildLst` 是递归过程,接收两个参数 `rootId`(当前节点ID)和 `nDepth`(当前深度)...

    JsTree 最详细教程及完整实例

    1. **节点(Nodes)**:在 JsTree 中,每个元素都被称为一个节点。节点可以有父节点和子节点,形成层级关系。 2. **配置(Configuration)**:JsTree 提供了大量的配置选项,允许用户定制其行为和外观。例如,你...

Global site tag (gtag.js) - Google Analytics