Viiisit [LeetCode] - 222. Count Complete Tree Nodes

keep learning, keep coding!

Problem - Count Complete Tree Nodes

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.

翻譯蒟蒻

給定一個完全二元樹的根節點，返回樹中節點的總數。Wikipedia 解釋完全二元樹是一種樹結構，其每一層（除了可能是最後一層）都是完全填滿的，而最後一層的所有節點都盡可能地靠左。在最後一層的高度為 h 時，最後一層的節點數介於 1 和 2^h（含）之間。這個問題要求設計時間複雜度不超過 O(n) 的演算法。意即：算法的執行時間應該隨著節點數量的增加而呈線性增長。

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

通過遞迴遍歷整個樹，計算並返回樹中的節點數量。

Solution - 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 == null) return 0;
  return 1 + countNodes(root.left) + countNodes(root.right);
};

Solution - Ruby

def count_nodes(root)
  return 0 if root.nil?
  1 + count_nodes(root.left) + count_nodes(root.right)
end

Solution - PHP

function countNodes($root) {
  if (!$root) return 0;
  return 1 + $this->countNodes($root->left) + $this->countNodes($root->right);
}

LeetCode 傳送門 - Count Complete Tree Nodes