下面是一个示例代码,用于遍历树并计算特殊节点的总和:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def calculate_special_nodes_sum(root):
if root is None:
return 0
total_sum = 0
stack = [(root, False)] # 使用栈来迭代遍历树,同时记录每个节点是否已经被访问过
while stack:
node, visited = stack.pop()
if visited:
# 如果节点已经被访问过,将其值加到总和中
total_sum += node.val
else:
# 如果节点还没有被访问过,将其右子节点和左子节点按相反的顺序入栈
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
# 将当前节点标记为已访问
stack.append((node, True))
return total_sum
# 创建一个示例树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 计算特殊节点的总和
special_nodes_sum = calculate_special_nodes_sum(root)
print("特殊节点的总和为:", special_nodes_sum)
在这个示例代码中,我们定义了一个TreeNode
类来表示树的节点。每个节点具有一个值val
,以及左子节点left
和右子节点right
。
calculate_special_nodes_sum
函数用于遍历树并计算特殊节点的总和。我们使用一个栈来迭代遍历树,同时记录每个节点是否已经被访问过。栈的每个元素是一个元组(node, visited)
,其中node
表示节点,visited
表示该节点是否已经被访问过。
在遍历过程中,我们首先将根节点和False
(表示还没有被访问过)入栈。然后,每次从栈中弹出一个元素,如果该元素的visited
为True
,则将该节点的值加到总和中;否则,将该节点以及其右子节点和左子节点按相反的顺序入栈,并将该节点标记为已访问。
最后,返回总和作为结果。
在示例中,我们创建了一个示例树,并使用calculate_special_nodes_sum
函数计算特殊节点的总和。最终,输出特殊节点的总和为14。
上一篇:遍历双重排序表
下一篇:遍历树并找到一个节点