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) {//判断当前节点，为空返回0
return 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;
}
}
}
