原始问题:
编写递归算法,分别采用全局变量和函数返回值两种方式返回二叉树上度为2的结点个数
采用全局变量方式:
count = 0 # 全局变量,记录度为2的结点个数
def count_degree_2(root):
global count
if root is None:
return
if root.left and root.right: # 如果左右子树都存在,则该结点度为2
count += 1
count_degree_2(root.left)
count_degree_2(root.right)采用函数返回值方式:
def count_degree_2(root):
if root is None:
return 0
left_count = count_degree_2(root.left)
right_count = count_degree_2(root.right)
if root.left and root.right: # 如果左右子树都存在,则该结点度为2
return left_count + right_count + 1
else:
return left_count + right_count以上两种方式都是基于二叉树的遍历实现的,时间复杂度为O(n),其中n为二叉树的结点个数。
Prev:谈谈你这学期学习形势与政策的心得