LeetCode:完全二叉树节点个数

222. 完全二叉树的节点个数

思路：

如果是完全二叉树，则其结点的个数为 2^h-1；h为二叉树高度。
对根结点来说，如果根结点的左子树高度等于右子树高度，则左子树必为完全二叉树，总结点数量为 2^(左子树高度)-1 +1(根节点) +右子树结点数量。
如果左右子树高度不等，则右子树必为完全二叉树，总结点数量为 2^(右子树高度)-1 +1(根节点) +左子树结点数量。
右子树和左子树结点数量，可以递归求解。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root)
            return 0;
        int ans=solve(root);
        return ans;
    }
    
    int solve(TreeNode* node)
    {
        if(!node)   
            return 0;
        int ldep=Depth(node->left);
        int rdep=Depth(node->right);
        //如果左右子树深度相等，左子树为完全二叉树，可以用公式求结点数量，递归求解右子树
        if(ldep==rdep)    
            return (1<<ldep)+solve(node->right);
        //如果左右子树深度不等，右子树为完全二叉树，可以用公式求结点数量，递归求解左子树
        else                    
            return (1<<rdep)+solve(node->left);
    }
     //返回当前结点的深度
    int Depth(TreeNode *node)
    {
        if(!node)
            return 0;
        int n=0;
        while(node)
        {
            node=node->left;
            ++n;
        }
        return n;
    }
};

附判断是否是完全二叉树

思路：
根据完全二叉树特点，采用层序遍历。

1. 如果当前结点 不存在左结点，但存在右结点，那么一定不是完全二叉树。
2. 如果当前结点 存在左结点，并不存在右结点 或 左右结点均不存在，那么之后的所有结点都必须是叶节点。
3. 如果当前结点既存在左结点，又存在右结点，那么当前结点是完全二叉树的非叶节点。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
        queue<TreeNode *> q;
        q.push(root);
        bool state=false;  //用于判断当前结点 之后的所有结点是否必须为叶结点
        while(!q.empty())
        {
            TreeNode *tmp=q.front();
            if(tmp->left==NULL&&tmp->right!=NULL)  //第一种情况
                return false;
            if(state&&(tmp->left!=NULL||tmp->right!=NULL)) //第二种情况
                return false;
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
            else   //右结点为空，开启 叶节点判断
                state =true;
        }
        return true;
    }
};

第二种情况，其实是只要 一个结点，并不是左右子结点全都存在，则层序遍历中，其后的所有结点必须是叶节点。
而 不存在左结点，存在右结点， 是第一种情况；
还剩 即不存在左，又不存在右 和 存在左，不存在右；这两种情况可以统一为 右是否存在。若当前结点不存在右结点，则开启其后所有结点都必须是叶结点这一判断。