leetcode-222

leetcode 222

/**
* 2019:10:25
* leetcode-cn-222
* icenaive
*/

/**
* 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 {
private:
   int n = 0;
   void dfs(TreeNode *root) {
       //if(!root) return 0;
       n += 1;
       if(root->left) dfs(root->left);
       if(root->right) dfs(root->right);
   }
public:
   int countNodes(TreeNode* root) {
       if(!root) return n;
       dfs(root);
       return n;
   }

   // 利用完全二叉树特点进行计算，
   /*
   * 对于一个完全二叉树：它是一棵空树或者它的叶子节点只出在最后两层，若最后一层不满则叶子节点只在最左侧。
   * 满二叉树节点计算，高度为h： 总结点数为2^h-1
   * 对于完全二叉树来说。从根节点开始 统计树的左子树和和右子树的高 left 和 right
   * 两种情况：
   * left == right：
   *   root的左子树就是满二叉树，因为他的右子树高度与左子树高度相同， 所以节点个数为2^left - 1 加上根为 2^left
   * left != right:
   *   肯定是left > right的情况，这种情况下right肯定会是满二叉树，高度比左-1，所以节点数为2^right - 1, 加上根：2^right;
   * 计算2^h的时候可以通过移位运算符，但是需要注意优先级，加上括号
   * 不过还是递归快
   */
   int countNodes(TreeNode *root) {
       if(!root) {
           return 0;
       }
       int left = countLevel(root->left);
       int right = countLevel(root->right);

       if(left == right) return countNodes(root->right) + (1 << left);
       else return countNodes(root->left) + (1 << right);
   }

   int countLevel(TreeNode *root) {
       if(!root) return 0;
       int level = 0;
       while(root) {
           ++level;
           root = root->left;
       }
       return level;
   }
};
// 别人的递归 好像我的结果跑出来还更优
class Solution{
public:
   int countNodes(TreeNode *root) {
   if(!root) return 0;
   return countNodes(root->left) + countNodes(root->right) + 1;
   }
};