- 浏览: 183473 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 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); } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 497Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 429Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 580Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 930Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 673Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 842Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 783You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 704For a undirected graph with tre ...
相关推荐
java java_leetcode题解之Count Complete Tree Nodes.java
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 ) {...
首先,我们需要创建一个名为 `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"的压缩包文件显然涉及到与树相关的两个操作:计算叶子节点的数量以及交换二叉树的左右子树。 首先,让我们详细探讨如何**计算叶子节点**(也称为终端节点)的数量...
GET /TreeNodes返回所有TreeNodes GET /TreeNodes/{id} -返回具有指定ID的TreeNode GET /TreeNodes/by-name/{name} -返回具有指定名称的TreeNode PUT /TreeNodes/{name}/update-name [body { newName: "string"}]...
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 ...
在Windows Forms(WinForms)应用开发中,我们经常会遇到数据展示和操作的需求,例如将`TreeNodes`(树形结构的节点)与`DataGrids`(数据网格)结合使用。`TreeNode`是`TreeView`控件的基本元素,用于表示层次化的...
反编译为 C#(查看语言支持状态)) 整个项目反编译 搜索类型/方法/属性(了解选项) 基于超链接的类型/方法/属性导航 基本/派生类型导航、历史记录 程序集元数据资源管理器(功能演练)) BAML 到 XAML 反编译器 ...
`count_struct_nodes(a_struct)`函数就是用于解决这个问题的,它能帮助我们计算一个结构体中所有非结构子元素的总数。 首先,让我们深入了解结构体的概念。在MATLAB中,结构体由一组字段(field)组成,每个字段都...
var selected_nodes = $('#jstree_demo_div').jstree('get_selected'); ``` **插件扩展** jsTree 具有一系列内置插件,如 `'checkbox'` 插件,用于实现多选功能;`'dnd'` 插件,用于拖放操作;`'search'` 插件,...
/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是一款基于JavaScript的开源库,专门用于构建交互式的树形视图。在网页开发中,树形结构常用于展示层级关系的数据,如目录、组织结构或导航菜单等。jsTree提供了丰富的API和可定制的...
在 SAP 系统中,ALVTREE 是一种用于展示层级数据的控件,它与标准的 TREE 控件有所不同。在标准的 ALVTREE 实现中,并没有提供预置的完全展开和完全合并的功能,因此在实际应用中,我们需要通过自定义的方式来实现...
nodes.dat文件是kad网络中存储节点信息的数据文件,它包含了一系列节点的标识符(ID)和它们的网络地址(IP地址和端口号)。在本篇详解中,我们将深入探讨如何对kad协议中的nodes.dat文件进行抓包分析,以及从这些...
从 tree2_demo.html 中我们可以学习到 Tree 的基本结构和配置,从 tree2_getdata.php 和 conn.php 学习到数据获取和处理的方法,而 nodes.sql 则帮助我们理解数据存储和组织的方式。对于想要学习和使用 EasyUI Tree ...
1. **节点 (Nodes)**:jsTree 中的基本元素,可以是树的根节点或子节点。每个节点包含文本、ID、图标等属性,并可拥有子节点。 2. **容器 (Container)**:通常是一个 HTML 元素,如 `div`,用于承载整个树结构。 3...
return Json(treeNodes, JsonRequestBehavior.AllowGet); } ``` 这里,`YourTreeNodeModel`是你自定义的节点模型,包含文本、ID和其他可能的属性。 至于压缩包中的文件`www.zzx8.com`和`H`,它们似乎并不是jstree...
java基础 java_leetcode题解之All Nodes Distance K in Binary Tree.java
select tmpLst.*,treeNodes.* from tmpLst,treeNodes where tmpLst.id=treeNodes.id order by tmpLst.sno; END ``` 2. `createChildLst` 是递归过程,接收两个参数 `rootId`(当前节点ID)和 `nDepth`(当前深度)...
1. **节点(Nodes)**:在 JsTree 中,每个元素都被称为一个节点。节点可以有父节点和子节点,形成层级关系。 2. **配置(Configuration)**:JsTree 提供了大量的配置选项,允许用户定制其行为和外观。例如,你...