完全二叉樹的節(jié)點個數(shù)
題目描述：給你一棵 完全二叉樹 的根節(jié)點 root 榄棵，求出該樹的節(jié)點個數(shù)。
完全二叉樹 的定義如下：在完全二叉樹中潘拱，除了最底層節(jié)點可能沒填滿外疹鳄，其余每層節(jié)點數(shù)都達到最大值，并且最下面一層的節(jié)點都集中在該層最左邊的若干位置芦岂。若最底層為第 h 層瘪弓，則該層包含 1~
個節(jié)點。
示例說明請見LeetCode官網(wǎng)禽最。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-complete-tree-nodes/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有腺怯。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處川无。
解法一：二叉樹的層序遍歷
對二叉樹層序遍歷呛占，按從上到下、從左到右的順序遍歷二叉樹懦趋，其中利用了隊列先進先出的特點晾虑。具體處理過程如下：
- 首先如果根節(jié)點為空，即為空樹仅叫，說明沒有節(jié)點帜篇，直接返回0；
- 否則诫咱，先將根節(jié)點添加到隊列中坠狡，然后遍歷隊列中的節(jié)點，直到隊列為空遂跟，遍歷過程中記錄節(jié)點的數(shù)目逃沿。
最后返回節(jié)點數(shù)婴渡。
import com.kaesar.leetcode.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
public class LeetCode_222 {
/**
* 二叉樹層序遍歷
*
* @param root
* @return
*/
public static int countNodes(TreeNode root) {
// 如果根節(jié)點為空，即為空樹凯亮，說明沒有節(jié)點边臼，直接返回0
if (root == null) {
return 0;
}
// 利用隊列先進先出的特性，對二叉樹進行層序遍歷
Queue<TreeNode> nodes = new LinkedList<>();
// 首先將根節(jié)點添加到隊列中假消，作為第一層
nodes.add(root);
// 記錄二叉樹的節(jié)點數(shù)
int count = 0;
// 遍歷隊列中的節(jié)點柠并，直到隊列為空
while (!nodes.isEmpty()) {
count++;
TreeNode cur = nodes.poll();
if (cur.left != null) {
nodes.add(cur.left);
}
if (cur.right != null) {
nodes.add(cur.right);
}
}
return count;
}
public static void main(String[] args) {
/**
* 測試用例：
* 1
* 2 3
* 4 5 6
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
// 期望輸出： 6
System.out.println(countNodes(root));
}
}
【每日寄語】 大丈夫行事，當(dāng)磊磊落落富拗，如日月皎然臼予。
