Topic describes
Given the root node of a complete binary tree, find the number of nodes in the tree.
A complete binary tree is defined as follows: In a complete binary tree, the number of nodes in each layer reaches the maximum except that the lowest node may not be filled, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is layer H, this layer contains 1 to 2h nodes.
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
Tip:
The number of nodes in the tree ranges from [0, 5 * 10410^4104] 0 <= node. val <= 5 * 10410^4104
Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
Antithesis thought
Based on the definition of full binary tree and subject known condition, to compute the description in the title of full binary tree node number, we can about each node of the node exists to count, existing node is accumulative count 1 and continue to recursive counting down, until meet leaf node (around nodes are not exist), starting each leaf node is 1, Each level up accumulates one parent node, and so on.
Answer key code
* 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; 0 let left = countNodes(root.left); // Recursively iterate over all left nodes let right = countNodes(root.right); Return left + right + 1; // Left node + right node + parent node is itself a minimum unit of measure};Copy the code