当前位置:实例文章 » 其他实例» [文章]剑指54二叉搜索树的第K大结点 55 二叉树的深度

剑指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代码实现。

相关标签:算法深度优先
其他信息

其他资源

Top