LeetCode 222 [Count Complete Tree Nodes]

题目链接

题目描述

  • 给定一棵完全二叉树,要求计算它的总结点数。完全二叉树指的是除了最后一层之外,其他每一层都是完整的,最后一层可能不是完整的,但是这一层的结点全部聚集在左侧,因此完全二叉树的结点数落在(1,2^h)这个区间内。

解题思路

  1. 一开始我使用最简单的方式来处理,完全二叉树是特殊的二叉树,只要把它的结点全部遍历一次就可以了。这种方法可以得到结果,但是时间复杂度为O(n),直接超时了。
  2. 接着我改进了计算方式,从最右侧开始遍历,当发现最后一层某个位置有结点的时候就停止。这种方法在平均情况下只需要遍历一半的结点,但是时间复杂度还是O(n),还是超时。
  3. 时间复杂度为O(n)行不通,只能考虑O(log n)的算法,而O(log n)的时间复杂度一般对应着二分法。对于这个题目,可以通过二分法查找最后一层的最后一个结点的位置,进而计算出总结点数,具体的算法如下:
    1. 首先计算树的高度,由根结点一直往左偏移,计算偏移次数即可,这一步的时间复杂度为O(log n)。
    2. 除了树为空或者仅有根结点的情况,完全二叉树的倒数第二层肯定是完整的,因此可以通过倒数第二层的结点来判断最后一层的结点的分布情况。
    3. 从根结点开始处理,以当前结点为中间线,将以当前结点为根的二叉树分成两部分,取倒数第二层中,左半部分最靠近中间线的结点,即之前描述的二分的方式。这个处于“二分位置偏左”的结点,称之为“二分结点”,必然是当前结点的左子树(不考虑原树最后一层)的最右边的结点。
    4. 如果“二分结点”有右子结点,说明上述的左半部分是完整的,继续考虑右半部分,将当前结点向它的右结点偏移。
    5. 如果“二分结点”没有右子结点,说明上述的左半部分不是完整的,右半部分最后一层的结点全部缺失,记录对应的缺失结点数之后,将当前结点向它的左结点偏移。
    6. 对新的当前结点进行处理,直到当前结点位于倒数第二层,这种情况下以当前结点为根的树(不考虑原树最后一层)仅有一个结点,无法拆分为左右两部分,因此直接根据它的左右子结点是否为空,对应记录缺失的结点数即可。
    7. 倒数第二层处理完之后,处理流程结束,计算相同高度的满二叉树的结点数,用它减去缺失的结点数,即为所求的完全二叉树的结点数。

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <math>
class Solution {
public:
    int countNodes(TreeNode* root) {
        // 计算树的高度
        int height = 0;
        TreeNode* tmp = root;
        while (tmp) {
            height++;
            tmp = tmp->left;
        }
        
        // 记录缺少的结点数
        int numRightEmpty = 0;
        
        TreeNode* node = root;
        TreeNode* curNode;
        int level = 1;
        int curLevel;
        
        // 从根结点开始遍历,直到当前结点为空,或者已遍历到最后一层
        while (node && level < height) {
            // 如果当前结点位于倒数第二层,则处理完它的子结点的情况之后即可结束
            if (level == height - 1) {
                numRightEmpty += node->right ? 0 : node->left ? 1 : 2;
                break;
            }
            
            // 以当前结点位置为中间线,查找倒数第二层里面,中间线偏左的最后一个元素
            // 查找方法为当前结点向左下方偏移,再一直向右下方偏移,直到倒数第二层为止
            curNode = node->left;
            curLevel = level + 1;
            while (curLevel < height - 1) {
                curNode = curNode->right;
                curLevel++;
            }
            
            // 如果中间线偏左的最后一个元素有右子结点,则需要将当前结点重置为它的右子结点
            // 如果中间线偏左的最后一个元素没有右子结点,那么说明当前结点缺少了右半边的叶子结点,对应处理之后,将当前结点重置为它的左子结点
            if (curNode->right) {
                node = node->right;
            } else {
                numRightEmpty += (int)pow(2.0, (double)(height - level - 1));
                node = node->left;
            }
            level++;
        }
        
        // 总的结点数为(2^h - 1 - 缺少的结点数)
        return (int)pow(2.0, (double)(height)) - 1 - numRightEmpty;
    }
};