.27若二叉树1采用二叉链表2存储结构,试编写算法,求该二叉树中值为2的结点所在的层数。
时间: 2025-01-05 08:48:27 浏览: 7
要编写一个算法来求二叉树中值为2的结点所在的层数,我们可以使用递归的方法遍历二叉树的每一个结点,并在遍历过程中记录当前的层数。以下是一个示例算法:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_level(root, target, current_level):
if root is None:
return 0
if root.val == target:
return current_level
level = find_level(root.left, target, current_level + 1)
if level != 0:
return level
return find_level(root.right, target, current_level + 1)
# 示例二叉树
# 1
# / \
# 2 3
# /
# 4
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
target_value = 2
level = find_level(root, target_value, 1)
print(f"值为{target_value}的结点所在的层数是: {level}")
```
在这个算法中,`find_level`函数接受三个参数:当前结点`root`,目标值`target`,以及当前的层数`current_level`。如果当前结点为空,返回0;如果当前结点的值等于目标值,返回当前的层数;否则,递归地查找左子树和右子树。
阅读全文