剑指54二叉搜索树的第K大结点 55 二叉树的深度
发布人:shili8
发布时间:2025-03-15 02:57
阅读次数:0
**剑指54二叉搜索树的第K大结点**
**剑指55二叉树的深度**
### 一、剑指54二叉搜索树的第K大结点####问题描述:
给定一棵二叉搜索树,找到第 K 大的结点值。
#### 示例:
输入:root = [5,3,18,10,null,12,15,null,null,6], k =3输出:10#### 思路:
1. 中序遍历二叉搜索树,得到一个有序数组。
2. 在这个有序数组中找到第 K 大的结点值。
### 二、剑指55二叉树的深度####问题描述:
给定一棵二叉树,求其最大深度。
#### 示例:
输入:root = [3,9,20,null,null,15,7]
输出:3#### 思路:
1. 使用递归或迭代法计算二叉树的深度。
### 三、代码实现####54二叉搜索树的第K大结点
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef kthLargest(root: TreeNode, k: int) -> int: """ :type root: TreeNode :type k: int :rtype: int """ # 中序遍历二叉搜索树,得到一个有序数组 def inorder(node): if not node: return [] return inorder(node.left) + [node.val] + inorder(node.right) # 在这个有序数组中找到第 K 大的结点值 nums = inorder(root) return nums[k-1]
####55二叉树的深度
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Nonedef maxDepth(root: TreeNode) -> int: """ :type root: TreeNode :rtype: int """ # 递归法计算二叉树的深度 if not root: return0 else: left_depth = maxDepth(root.left) right_depth = maxDepth(root.right) return max(left_depth, right_depth) +1
### 四、测试
# 测试54二叉搜索树的第K大结点root = TreeNode(5) root.left = TreeNode(3) root.right = TreeNode(18) root.left.left = TreeNode(10) root.left.right = TreeNode(12) root.right.right = TreeNode(15) root.left.left.right = TreeNode(6) print(kthLargest(root,3)) # 输出:10# 测试55二叉树的深度root = TreeNode(3) root.left = TreeNode(9) root.right = TreeNode(20) root.right.left = TreeNode(15) root.right.right = TreeNode(7) print(maxDepth(root)) # 输出:3
### 五、总结本文介绍了剑指54二叉搜索树的第K大结点和剑指55二叉树的深度两个问题,分别使用中序遍历和递归法计算二叉树的深度,并提供了Python代码实现。