题解 | #完全二叉树结点数#

/**
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
//本题利用Morris遍历统计节点数目可以轻松做到时间复杂度O（N）空间复杂度O（1）,但是就失去了本题的考察意义
//完全二叉树有独特的性质，可以这样来统计一颗完全二叉树的节点数目
//首先求出整棵树的高度，然后求以根节点的左孩子为头的树右边界的高度，如果高度恰好为以根节点为头的整棵树的高度减1
//说明以左孩子为头的整棵树是满二叉树，节点数目可以用常数时间求出，如果不满足这种关系，说明以右孩子为根的整棵树是满二叉树
//可以自行画图证明（根据完全二叉树的特点也很容易可以得到）
class Solution {
public:
    //该函数的含义为返回以root为根节点的完全二叉树的最大高度
    int lenth(TreeNode*root){
        if(root==NULL)
            return 0;
        int len=0;
        TreeNode*cur=root;
        while(cur){
            len++;
            cur=cur->left;
        }
        return len;
    }
    //该递归函数的含义为返回以root为根节点的完全二叉树的节点数
    int process(TreeNode*root)
    {
        if(root==NULL)
            return 0;
        int res=0;//最终的返回值
        //首先求出完全二叉树的最大高度
        int high=lenth(root);
        //然后求出左子树的右边界长度
        int mostRight=0;
        TreeNode*node=root->left;
        while(node){
            mostRight++;
            node=node->right;
        }
        //判断两者大小关系
        if(mostRight==high-1){//说明左子树是一颗满二叉树
            res+=pow(2, mostRight)-1+1+process(root->right);//2的n次方减1是满二叉树的节点计算公式,再加1是加的根节点
        }
        else{//说明右子树是一颗满二叉树
            res+=pow(2,high-2)-1+1+process(root->left);
        }
        return res;
    }
    int nodeNum(struct TreeNode* head) {
        return process(head);
    }
};