Shulou(Shulou.com)06/01 Report--

Python complete binary tree node number example analysis, in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

A complete binary tree is given, and the number of nodes of the tree is obtained.

Description:

The definition of a complete binary tree is 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 full, and the nodes in the lowest layer are concentrated in the leftmost positions of the layer. If the lowest layer is the h layer, the layer contains 1 ~ 2 hours of nodes.

Example:

Enter:

one

/\

2 3

/\ /

4 5 6

Output: 6

Ideas for solving the problem:

1, recursively traverse the entire binary tree, this method can be optimized

2, calculate the height of the left and right subtrees

A, if lquadr shows that the left subtree is a full binary tree and the number of nodes is 2 ^ l-1, the right subtree needs recursive computation.

B, if l=r+1 indicates that the right subtree is a full binary tree and the number of nodes is 2 ^ r-1, the left subtree needs to be calculated recursively.

3, the number of nodes of the tree is root (1) + the number of nodes of the left subtree + the number of nodes of the right subtree

/ * Definition for a binary tree node. * type TreeNode struct {* Val int * Left * TreeNode * Right * TreeNode *} * / func countNodes (root * TreeNode) int {if root==nil {return 0} l:=depth (root.Left) r:=depth (root.Right) if lags.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.