在一棵二叉树中,求以值为X的结点为根结点的子树的深度。算法设计
时间: 2024-03-16 14:42:18 浏览: 130
可以通过递归的方式来求以值为X的结点为根结点的子树的深度。
具体实现方法如下:
1. 首先判断根结点是否为X值,如果是则返回1。
2. 如果根结点不是X值,则递归地遍历左右子树,找到X值所在的结点,递归的过程中记录深度值。
3. 如果在左子树或右子树中找到了X值所在的结点,则返回深度值加1。
4. 如果左右子树都没有找到X值所在的结点,则返回0。
具体的代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def get_depth(root: TreeNode, x: int) -> int:
if not root:
return 0
if root.val == x:
return 1
left_depth = get_depth(root.left, x)
if left_depth > 0:
return left_depth + 1
right_depth = get_depth(root.right, x)
if right_depth > 0:
return right_depth + 1
return 0
```
其中,参数root表示二叉树的根结点,参数x表示要查找的结点的值,返回值为以值为X的结点为根结点的子树的深度。
阅读全文