給定一個完全二叉樹的根節點，返回樹中節點的數量。
根據維基百科，在完全二叉樹中，除了最後一層外，每一層都是完全填滿的，並且在最後一層的所有節點都盡可能地向左排列。它在最後一層 h 可以有介於 1 到 2^h 個節點（包含兩端）。
設計一個算法，其運行時間複雜度小於 O(n)。
範例：
輸入:
root = [1,2,3,4,5,6]
輸出:
輸入:
root = [1,2,3,4,5,6]
輸出:
6
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
# Helper function to compute the depth of the tree
def get_depth(node: TreeNode) -> int:
depth = 0
while node:
node = node.left
depth += 1
return depth
if not root:
return 0
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
if left_depth == right_depth:
# Left subtree is complete
return (1 << left_depth) + self.countNodes(root.right)
else:
# Right subtree is complete
return (1 << right_depth) + self.countNodes(root.left)
21.78MB, 22ms
C++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
if (leftDepth == rightDepth) {
// Left subtree is complete
return (1 << leftDepth) + countNodes(root->right);
} else {
// Right subtree is complete
return (1 << rightDepth) + countNodes(root->left);
}
}
private:
int getDepth(TreeNode* node) {
int depth = 0;
while (node) {
node = node->left;
depth++;
}
return depth;
}
};
29.33MB, 21ms
Javascript
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @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) {
// Left subtree is complete
return (1 << leftDepth) + countNodes(root.right);
} else {
// Right subtree is complete
return (1 << rightDepth) + countNodes(root.left);
}
};
68.76MB, 87ms
