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

后序遍历

  1. class Solution {
  2. private:
  3.     int getNodesNum(TreeNode* cur) {
  4.         if (cur == NULL) return 0;
  5.         int leftNum = getNodesNum(cur->left);      // 左
  6.         int rightNum = getNodesNum(cur->right);    // 右
  7.         int treeNum = leftNum + rightNum + 1;      // 中
  8.         return treeNum;
  9.     }
  10. public:
  11.     int countNodes(TreeNode* root) {
  12.         return getNodesNum(root);
  13.     }
  14. };

完全二叉树的性质

  1. 当完全二叉树为满二叉树时，结点数量为2^depth-1
  2. 当完全二叉树不是满二叉树时，分别递归左子树，和右子树，递归到某一深度一定会有左子树或者右子树为满二叉树，然后依然可以按照情况1来计算。、、
    1. class Solution {
    2. public:
    3.  int countNodes(TreeNode* root) {
    4.      if (root == nullptr) return 0;
    5.      TreeNode* left = root->left;
    6.      TreeNode* right = root->right;
    7.      int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
    8.      while (left) {  // 求左子树深度
    9.          left = left->left;
    10.          leftHeight++;
    11.      }
    12.      while (right) { // 求右子树深度
    13.          right = right->right;
    14.          rightHeight++;
    15.      }
    16.      //满二叉树
    17.      if (leftHeight == rightHeight) {
    18.          return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
    19.      }
    20.      //不是满二叉树，当前结点+1然后递归左右子树。
    21.      return countNodes(root->left) + countNodes(root->right) + 1;
    22.  }
    23. };