Leetcode:222.完全二叉树的节点个数
给出一个完全二叉树,求出该树的节点个数。
说明:
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。
示例:
输入: 1 / \ 2 3 / \ / 4 5 6 输出: 6
解题思路:
二分法。j假设整个树的高度为h,根据完全二叉树的特点:
1. 如果右子树的高度小于左子树,那么右子树是完美二叉树,高度为h-2。节点个数是(1<<h-1)-1。
2. 如果右子树的高度等于左子树,那么左子树为完美二叉树,高度为h-1。节点个数是(1<<h)-1。
从根结点开始,根据左右子树的高度总是能够确定左边或者右边的结点个数,然后递归到不确定的一端即可。其中求解子树高度的平均时间是0.5logn,递归次数是logn,这样一来时间复杂度为(log n)*(log n)。
class Solution { public: int countNodes(TreeNode* root) { if (!root) return 0; int h = 0; TreeNode* node = root; while (node) { h++; node=node->left; } //至少有h-1层是满树 int nums = (1 << h - 1) - 1; node = root; while (node) { TreeNode *right = node->right; if (!right) { nums++; break; } int temp_h = 0; while (right) { temp_h++; right = right->left; } if (temp_h + 1 == h) { nums += 1 << (h - 2); node = node->right; h = h - 1; } else { node = node->left; h = h - 1; } } return nums; } }; |