题目:
给出一个完全二叉树,求出该树的节点个数。
示例 1:
- 输入:root = [1,2,3,4,5,6]
- 输出:6
示例 2:
- 输入:root = []
- 输出:0
示例 3:
- 输入:root = [1]
- 输出:1
提示:
- 树中节点的数目范围是[0, 5 * 10^4]
- 0 <= Node.val <= 5 * 10^4
- 题目数据保证输入的树是 完全二叉树
题解:
1.以普通二叉树来解
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int countL = countNodes(root.left); int countR = countNodes(root.right); return countL + countR + 1; } }
2.以完全二叉树来解
有两种情况:
1.左右子树深度相同,此时左子树为满二叉树
2.左右子树深度不相同,此时右子树为满二叉树
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37/** * Definition for a binary tree node. * 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; * } * } */ class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int depthL = getDepth(root.left); int depthR = getDepth(root.right); if (depthL == depthR) { //左子树为满二叉树 return (1 << depthL) - 1 + countNodes(root.right) + 1; //左子树(depthL次乘以2,2^depthL) + 根结点 } else { //右子树为满二叉树 return (1 << depthR) - 1 + countNodes(root.left) + 1; } } public int getDepth(TreeNode root) { //因为是完全二叉树,最左边的深度为最终深度,这里求深度可以一直遍历左子树 if (root == null) { return 0; } return Math.max(getDepth(root.left), getDepth(root.right)) + 1; } }
参考:代码随想录
最后
以上就是爱撒娇灯泡最近收集整理的关于【二叉树】222. 完全二叉树的节点个数题目:题解:1.以普通二叉树来解的全部内容,更多相关【二叉树】222.内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复