华为od机试真题 python 实现【查找二叉树节点】

题目描述：

输入一个二叉查找树和一个目标节点值，输出这个目标节点在二叉查找树中的层数。如果这个节点不在树中，输出-1。

算法思路：

二叉查找树能快速找到目标节点，因为左边节点小于右边节点，可以用二分思想来优化查找速度。通过递归，比较当前节点值和目标节点值的大小，若相等则返回当前层数即可，若目标节点值小于当前节点值，则向左子树递归查找，否则向右子树递归查找。如果找到节点则返回当前层数，如果递归到叶子节点仍未找到，返回-1。

代码实现：

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def searchBST(self, root: TreeNode, val: int) -> int:
if root.val == val:
return 1
elif val < root.val and root.left:
return self.searchBST(root.left, val) + 1
elif val > root.val and root.right:
return self.searchBST(root.right, val) + 1
else:
return -1

测试样例：

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

s = Solution()
print(s.searchBST(root, 2)) # 2
print(s.searchBST(root, 5)) # -1

代码解释：

首先定义了一个节点类，包含节点值、左子树和右子树。然后是主要代码部分，将树的根节点和目标节点值作为参数传入函数中。如果当前节点值等于目标节点，则返回当前层数1。如果目标节点值小于当前节点值，且左子树存在，则将目标节点值和左子节点作为参数递归调用函数，返回值加1。如果目标节点值大于当前节点值，且右子树存在，则将目标节点值和右子节点作为参数递归调用函数，返回值加1。如果目标节点不在树中，返回-1。最后的测试样例中，对于二叉树的根节点的左子树中的值为2的节点，输出的结果是2；对于不存在于二叉树中的节点值为5的节点，输出的结果是-1。