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

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

写出中序迭代和完全二叉树特性解法

class Solution {
public:
    int dfs(TreeNode* root){
        if(!root) return 0;
        TreeNode* leftnode = root->left;
        TreeNode* rightnode = root->right;
        int leftdep = 0,rightdep = 0;
        while(leftnode){
            leftnode = leftnode->left;
            leftdep++;
        }
        while(rightnode){
            rightnode = rightnode->right;
            rightdep++;
        }
        if(leftdep == rightdep) return (2<-1;
 
        return  dfs(root->left)+dfs(root->right)+1;
    }
    int countNodes(TreeNode* root) {
        //使用完全二叉树
        //遍历每一个结点，查看他构成的树是否满了；
        return dfs(root);
    }
};
 
class Solution {
public:
    int countNodes(TreeNode* root) {
        //中序
        stackst;
        int count = 0;
        //左中右
        if(!root) return count;
        TreeNode* cur = root;
        while(cur || !st.empty()){
           if(cur){
               st.push(cur);
               cur = cur->left;
           }
           else{
               cur = st.top();
               st.pop();
               count++;
               cur = cur->right;
           }
        }
        return count;
    }
};