3-3-完全二叉树结点数

1 /*
2 思路： 其实也是一种二分的思路。
3 因为是完全二叉树，所以可以分为根结点的左右子树计算节点个数。
4 首先求得该完全二叉树的深度h。
5 然后判断根结点的右子树的最左节点是否在深度h上，
6 如果在，则说明该完全二叉树的左子树为一个深度为h-1的满二叉树，
7 其结点个数有：2^(h-1)-1个，加上根结点，结点总个数为2^(h-1)。
8 最后在对右子树进行递归求解其节点个数。
9 如果右子树的最左结点不再深度h上，则说明其右子树为一个深度为h-2的满二叉树，
10 其结点个数有：2^(h-2)-1个，加上根结点，结点总个数为2^(h-2)。
11 最后再对左子树进行递归求解结点个数。
12 
13 转换为一般情况：若此时根结点处于
14 */
15 #include <iostream>
16 using namespacestd;
17 
18 structTreeNode {
19     intval;
20     struct TreeNode *left;
21     struct TreeNode *right;
22     TreeNode(intx) :
23 val(x), left(NULL), right(NULL) {
24 }
25 };
26 
27 int mostLeftDepth(struct TreeNode* head, int level){    //求head的最左节点所处的深度
28     while (head !=NULL){
29         level++;
30         head = head->left;
31 }
32     return level-1;
33 }
34 int bs(struct TreeNode* head, int l, inth){
35     if (l ==h)
36         return 1;
37     if (mostLeftDepth(head->right,l+1) ==h)
38         return (1 << (h-l)) + bs(head->right, l+1, h);
39     else
40         return (1 << (h-l-1)) + bs(head->left, l+1, h);
41 }
42 
43 int nodeNum(struct TreeNode*head) {
44     if (head ==NULL)
45         return 0;
46     return bs(head, 1, mostLeftDepth(head,1));
47 }
48 
49 intmain(){
50     TreeNode* head = new TreeNode(1);
51     TreeNode* a = new TreeNode(2);
52     head->left =a;
53     TreeNode* b = new TreeNode(3);
54     head->right =b;
55     cout << nodeNum(head) <<endl;
56     return 0;
57 }