222. 完全二叉树的节点个数

🟢   🔖  位运算 树 二分查找 二叉树  🔗 力扣 LeetCode

题目

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia , every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

Input: root = [1,2,3,4,5,6]

Output: 6

Example 2:

Input: root = []

Output: 0

Example 3:

Input: root = [1]

Output: 1

Constraints:

• The number of nodes in the tree is in the range [0, 5 * 10^4].
• 0 <= Node.val <= 5 * 10^4
• The tree is guaranteed to be complete.

题目大意

输出一颗完全二叉树的结点个数。

解题思路

思路一：层序遍历

按照层序遍历一次树，然后把每一层的结点个数相加即可。

---

思路二：递归

关键思想是比较左右子树的深度。如果它们相等，左子树是一个满二叉树，节点总数可以直接计算 (2 ^ i - 1)。如果深度不相等，右子树是一个满二叉树，节点总数也可以根据深度计算。递归调用处理两个子树，直到达到基本情况（一个空节点）。

• countNodes 函数以完全二叉树的根节点作为输入，递归计算节点的数量。
• getDepth 函数通过遍历左孩子直到叶子节点，计算给定节点的深度。

代码

层序遍历

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
	let res = 0;
	if (!root) return res;
	let queue = [root];
	while (queue.length) {
		let len = queue.length;
		for (let i = 0; i < len; i++) {
			if (queue[i].left) queue.push(queue[i].left);
			if (queue[i].right) queue.push(queue[i].right);
			res++;
		}
		queue = queue.slice(len);
	}
	return res;
};

递归

/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function (root) {
	if (!root) return 0;

	const getDepth = (node) => {
		let depth = 0;
		while (node) {
			node = node.left;
			depth++;
		}
		return depth;
	};

	let leftDepth = getDepth(root.left);
	let rightDepth = getDepth(root.right);

	if (leftDepth == rightDepth)
		return Math.pow(2, leftDepth) + countNodes(root.right);
	return Math.pow(2, rightDepth) + countNodes(root.left);
};

相关题目

题号	标题	题解	标签	难度
270	最接近的二叉搜索树值 🔒		树 深度优先搜索 二叉搜索树 2+