给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6
这里给出两种实现方式,其一是深度优先搜索,将数据装载到集合中,返回集合的size即可,其二是使用递归的方式解决,递归的本质还是系统栈
import java.util.ArrayList;
import java.util.List;
public class CountNodesTest3 {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(1);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(3);
TreeNode t4 = new TreeNode(4);
TreeNode t5 = new TreeNode(5);
TreeNode t6 = new TreeNode(6);
t1.left = t2;
t1.right = t3;
t2.left = t4;
t2.right = t5;
t3.left = t6;
int countNodes = countNodes2(t1);
System.out.println("countNodes = " + countNodes);
}
public static int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
public static int countNodes2(TreeNode root) {
if (root == null) {
return 0;
}
List<Integer> list = new ArrayList<>();
dfs(root, list);
return list.size();
}
private static void dfs(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
if (root.left != null) {
dfs(root.left, list);
}
list.add(root.val);
if (root.right != null) {
dfs(root.right, list);
}
}
}
其实这道题我们可以使用各种各样的方式进行操作的,比如说我们也可以使用队列的方式进行操作,其本质原因还是利用容器装载数据元素,返回队列元素个数的