剑指54二叉搜索树的第K大结点 55 二叉树的深度

**剑指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]

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