2叉树节点个数.

来源:百度知道 编辑:UC知道 时间:2024/09/21 01:27:34
现在有一个2叉树,大概有100+的节点.目前每个节点的值(data)为在本节点下面的节点数(通俗的说法就是你手下的人数),现在新建一个2叉树时统统设为0.现在求一个方法当遍历2叉树一遍后其值(data)也相应的改变为其手下人数.要求效率.理想的情况是o(N)就最好了.

采取后根遍历的非递归算法即可.
遇到叶结点时,将其data=0,遇到非叶结点时,其手下肯定已经遍历过了,只要把其左右孩子的data相加,结果赋给其data即可 '

用递归算法也行,理论上的复杂度也是O(n),但实际运行中考虑到递归的消耗,比较慢一点