Java解决完全二叉树的节点个数
01 题目
-
给你一棵 完全二叉树 的根节点
root，求出该树的节点个数。完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第
h层，则该层包含1~ 2h个节点。示例 1：
输入：root = [1,2,3,4,5,6] 输出：6示例 2：
输入：root = [] 输出：0示例 3：
输入：root = [1] 输出：1提示：
- 树中节点的数目范围是
[0, 5 * 104] 0 <= Node.val <= 5 * 104- 题目数据保证输入的树是 完全二叉树
- 树中节点的数目范围是
02 知识点
- 二叉树
- 优先深度搜索
- 剪枝
03 我的题解思路
public class countNodes {
// 几个常用二叉树函数root.val当前节点值，root.left二叉树左节点，root.right二叉树右节点public static int countNodes(TreeNode root) {if(root==null) {//判断当前节点，为空返回0return 0;}//判断左节点是否为空，为空返回当前节点值1（题设优先左节点，无左节点也就没右节点），不为空继续递归（简单理解为利用函数循环）if(root.left==null) {return 1;}else {countNodes(root.left);}if(root.left!=null) {//判断右节点是否为空，不为空递归，为空，不继续遍历countNodes(root.right);}return 1+countNodes(root.left)+countNodes(root.right);}
// 二叉树public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
}
