二叉树的叶子节点、第K层节点/数组中数字次数超过数组长度的一般_当前结点的层数大于结点数组的长度

//一个数组中有一个数字的次数超过了数组的一半，求出这个字符。
//如：int a[] = { 2, 3, 2, 2, 2, 2, 2, 5, 4, 1, 2, 3 }，求出超过一半的数字是2。
//我这里用来两种方法，第一种可以用哈希表来统计次数来解决这个问题。第二种是num出现的次数，出现一次num++，没有出现num--,当num减到0时，字符重新改变。因为出现的次数大于数组长度的一般，所以遍历完数组这个字符的num大于0的
int PassHalf(int* a, int len)
{
    if (a == NULL || len < 0)
    {
        return -1;
    }
    int i = 0;
    int num = 0;
    int key = 0;
    for (i = 0; i < len; i++)
    {
        if (num == 0)
        {
            key = a[i];
        }
        if (a[i] == key)
        {
            num++;
        }
        else
        {
            num--;
        }
    }
    return key;
}
//int PassHalf(int* a, int len)
//{
//  int i = 0;
//  int temp[1024] = { 0 };
//  for (i = 0; i < len; i++)
//  {
//      temp[a[i]]++;
//  }
//  for (i = 0; i < sizeof(temp)/sizeof(temp[0]); i++)
//  {
//      if (temp[i]>len / 2)
//      {
//          return i;
//      }
//  }
//}
int main()
{
    int a[] = { 2, 3, 2, 2, 2, 2, 2, 5, 4, 1, 2, 3 };
    int len = sizeof(a) / sizeof(a[0]);
    cout << PassHalf(a, len) << endl;
    system("pause");
    return 0;
}
//求二叉树叶子节点的个数 / 求二叉树第k层的节点个数。

/*struct BinaryNode
{
    int _val;
    BinaryNode* _left;
    BinaryNode* _right;
    BinaryNode(int x)
        :_val(x)
        , _left(NULL)
        , _right(NULL)
    {}
};
class Binarytree
{
public:
    typedef BinaryNode Node;
    Binarytree()
        :_root(NULL)
    {}
    Binarytree(int* a, int n, int invalid = int())//先构建左子树，再构建右子树
    {
        int index = 0;
        _root=_createtree(a, n, index, invalid);
    }
    ~Binarytree()
    {
        _Destroy(_root);
    }
    int LeafSize()//叶子节点的个数
    {
        int count = 0;
        _leafsize(_root,count);
        return count;
    }
    int GetLevel(int k)//第K层节点的个数
    {
        return _getlevel(_root,k);
    }
protected:
//根节点为第0层
    int _getlevel(Node* root,int k)
    {
        if (root == NULL)
        {
            return 0;
        }
        if (k == 0)
        {
            return 1;
        }
        return _getlevel(root->_left, k - 1) + _getlevel(root->_right, k - 1);

    }
    //计算叶子节点的个数
    void _leafsize(Node* root,int& count)
    {
        if (root == NULL)
        {
            return ;
        }
        if (root->_left == NULL&&root->_right == NULL)//左右子树为空时count++
        {
            count++;
        }
        _leafsize(root->_left,count);//走左子树
        _leafsize(root->_right,count);//走右子树

    }
    //数组要往后走，所以这里index用引用
    Node* _createtree(int* a, int n, int& index, int invalid)
    {
        Node* root = NULL;
        if (index < n&&a[index] != invalid)
        {
            root = new Node(a[index]);
            root->_left = _createtree(a, n, ++index, invalid);
            root->_right = _createtree(a, n, ++index, invalid);

        }
        return root;
    }
    void _Destroy(Node* root)
    {
        if (root != NULL)
        {
            _Destroy(root->_left);
            _Destroy(root->_right);
            delete root;
        }
    }
protected:
    Node* _root;
};
int main()
{
    int a[10] = { 1, 2, 3, 0, 0, 4, 0, 0, 5, 6 };
    int len = sizeof(a) / sizeof(a[0]);
    Binarytree t(a, len, 0);
    cout << t.LeafSize() << endl;
    cout << t.GetLevel(0) << endl;
    system("pause");
    return 0;

}*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158