LeetCode-222. Count Complete Tree Nodes

LeetCode-222. Count Complete Tree Nodes

​​a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from ​​Wikipedia​​: In a complete binary tree every level, except possibly the last, is completely filled, 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.

Example:

Input: 1 / \ 2 3 / \ /4 5 6Output: 6

题解：原来直接返回1 + countNodes(root->left) + countNodes(root->right)会报超时，看别人分析，满二叉树可以单独处理。

class Solution {public: int countNodes(TreeNode* root) { TreeNode *p = root, *q = root; if (!root){ return 0; } int l = 0, r = 0; while (p){ l++; p = p->left; } while (q){ r++; q = q->right; } if (r == l){ return pow(2, l) - 1; } return 1 + countNodes(root->left) + countNodes(root->right); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。