7. 编写递归算法:求二叉树中以元素值为x的结点为根的子树的深度。
时间: 2024-12-22 07:18:19 浏览: 9
编写递归算法求解二叉树中以元素值为x的节点作为根的子树深度,我们可以按照以下步骤设计:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def subtree_depth(root, x, depth=0):
if root is None:
return depth
# 如果当前节点的值等于目标值x,则更新深度并返回
if root.val == x:
return depth + 1
# 否则,分别递归计算左子树和右子树的深度
left_depth = subtree_depth(root.left, x, depth+1) if root.left else 0
right_depth = subtree_depth(root.right, x, depth+1) if root.right else 0
# 返回较大的子树深度,因为子树的深度应该是当前节点加上更深的那个子树的深度
return max(left_depth, right_depth)
# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(x) # 假设我们要查找的元素x在此处
target_depth = subtree_depth(root, x)
print(f"以值 {x} 为根的子树深度为: {target_depth}")
```
在这个递归函数中,我们首先检查当前节点是否为空,如果为空则返回当前深度;接着检查当前节点的值是否等于目标值x,如果是,则增加深度并返回;最后递归地遍历左右子树,并取最大深度作为结果。
阅读全文