LeetCode#222

LeetCode#222完全二叉树的节点个数

(题目链接)[https://leetcode-cn.com/problems/count-complete-tree-nodes/]
题目如题面所示。。。最简单的方法当然是直接遍历整个二叉树一遍了，但是这样的方法很傻（且不够快）。我们可以利用完全二叉树的性质，将代码写的更优雅一点。
完全二叉树最主要的性质就是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。因此我们可以有如下操作：递归的访问一个节点的左子节点，直到叶子节点，并将这个深度记为左深度；再一直访问这个节点的右子节点，并将这个深度记为右深度，如果一个节点的左深度=右深度，那么以这个节点为根的完全二叉树就一定是满二叉树（如果不懂的话找个纸画一画就知道了。。。）如果是满二叉树，它的节点个数就很好算了吧。
如果我们把这个判断是否为满二叉树的函数成为find，那么如果一个节点node为根的二叉树不是满二叉树，这棵树的节点个数sum就一定为：sum=find(node->left)+find(node->right)+1（还有根节点本身，所以+1），用这个思路进行递归，再进行亿点点的细节优化，这道题就很简单了。
上代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int find(TreeNode *node){
        if(node==nullptr)
            return 0;
        int left=0,right=0;
        TreeNode *templeft=node->left;
        while(templeft!=nullptr)//左层数
        {
            left++;
            templeft=templeft->left;
        }
        TreeNode *tempright=node->right;
        while(tempright!=nullptr)//右层数
        {
            right++;
            tempright=tempright->right;
        }  
        if(left==right)
        {
            int temp=0;
            int j=1;
            for(int i = 1 ; i <= left ; i++)
                {
                    j*=2;
                    temp+=j;
                }
            return temp+1;//满二叉树也要加当前节点
        }
        else
            return  find(node->left)+find(node->right)+1; 
    }
    int countNodes(TreeNode* root) {
        return find(root);
    }
};