请使用一种程序设计语言改写二叉树的一种深度优先遍历算法,要求能够计 算出每个顶点的深度。
时间: 2023-06-09 20:05:02 浏览: 161
求二叉树深度程序谢谢捧场
好的,我可以使用Python编写一个深度优先遍历算法来计算每个节点的深度。代码如下:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_helper(node, depth, depth_dict):
depth_dict[node] = depth
if node.left:
dfs_helper(node.left, depth+1, depth_dict)
if node.right:
dfs_helper(node.right, depth+1, depth_dict)
def dfs(root):
if root is None:
return {}
depth_dict = {}
dfs_helper(root, 0, depth_dict)
return depth_dict
# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
depths = dfs(root)
for node, depth in depths.items():
print(f"Node {node.val} has depth {depth}")
```
在这个例子中,我们定义了一个 `TreeNode` 类来表示我们的二叉树。然后我们编写了一个名为 `dfs_helper` 的递归函数来遍历整棵树,同时跟踪每个节点的深度,并使用一个字典来记录每个节点的深度。最后,我们定义了一个名为`dfs`函数来调用`dfs_helper`函数,然后返回每个节点的深度字典。我们可以使用上面的代码来计算出每个节点的深度。
阅读全文