Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
1.先向最左和最右走，看是否是满二叉树；如果是可以直接算法节点数目；
2.否则，对根的左右节点递归上述过程。
/** * 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 countNodes(TreeNode* root) { int hl = 0, hr = 0; TreeNode* l = root, *r = root; while (l){ l = l->left; hl++; } while (r){ r = r->right; hr++; } if (hl == hr) return (1 << hl) - 1; else{ return 1 + countNodes(root->left) + countNodes(root->right); } } };
