跳转至

3831. 二叉搜索树某一层的中位数 🔒

题目描述

给定一棵 二叉搜索树（BST）的根结点 root 和一个整数 level。

根节点位于第 0 层。每一层代表与根节点的距离。

返回给定 level 中所有节点值的中位数。如果该层不存在或没有节点，则返回 -1。

中位数 定义为将该层的值按 非降序 排序后中间的元素。如果该层的值的数量为偶数，则返回 向上 中位数（排序后两个中间元素中较大的那个）。

 

示例 1：

输入：root = [4,null,5,null,7], level = 2

输出：7

解释：

位于 level = 2 的节点是 [7]。中位数是 7。

示例 2：

输入：root = [6,3,8], level = 1

输出：8

解释：

位于 level = 1 的节点是 [3, 8]。有两个可能的中位数，因此较大的那个 8 是答案。

示例 3：

​​​​​​​

输入：root = [2,1], level = 2

输出：-1

解释：

在 level = 2​​​​​​​ 没有节点，所以答案是 -1。

 

提示：

  • 树中节点的数量在 [1, 2 * 105] 范围内。
  • 1 <= Node.val <= 106
  • 0 <= level <= 2 * 10​​​​​​​5

解法

方法一：DFS

我们注意到，题目要求我们找到二叉搜索树中某一层的节点值的中位数。由于中位数的定义是将节点值排序后取中间的值，而二叉搜索树的中序遍历本身就是有序的，因此我们可以通过中序遍历来收集指定层级的节点值。

我们定义一个辅助函数 \(\text{dfs}(root, i)\)，其中 \(root\) 是当前节点，而 \(i\) 是当前节点的层级。在函数中，如果当前节点为空，则直接返回。否则，我们递归地遍历左子树，检查当前节点的层级是否等于目标层级，如果是，则将当前节点的值加入结果列表中，最后递归地遍历右子树。

我们初始化一个空列表 \(\text{nums}\) 来存储指定层级的节点值，并调用 \(\text{dfs}(root, 0)\) 来开始遍历。最后，我们检查 \(\text{nums}\) 是否为空，如果为空则返回 -1，否则返回 \(\text{nums}\) 中间位置的值。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是树中节点的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelMedian(self, root: Optional[TreeNode], level: int) -> int:
        def dfs(root: Optional[TreeNode], i: int):
            if root is None:
                return
            dfs(root.left, i + 1)
            if i == level:
                nums.append(root.val)
            dfs(root.right, i + 1)

        nums = []
        dfs(root, 0)
        return nums[len(nums) // 2] if nums else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> nums = new ArrayList<>();
    private int level;

    public int levelMedian(TreeNode root, int level) {
        this.level = level;
        dfs(root, 0);
        return nums.isEmpty() ? -1 : nums.get(nums.size() / 2);
    }

    private void dfs(TreeNode root, int i) {
        if (root == null) {
            return;
        }
        dfs(root.left, i + 1);
        if (i == level) {
            nums.add(root.val);
        }
        dfs(root.right, i + 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int levelMedian(TreeNode* root, int level) {
        vector<int> nums;

        auto dfs = [&](this auto&& dfs, TreeNode* node, int i) -> void {
            if (!node) {
                return;
            }
            dfs(node->left, i + 1);
            if (i == level) {
                nums.push_back(node->val);
            }
            dfs(node->right, i + 1);
        };

        dfs(root, 0);
        return nums.empty() ? -1 : nums[nums.size() / 2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelMedian(root *TreeNode, level int) int {
    nums := make([]int, 0)

    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, i int) {
        if node == nil {
            return
        }
        dfs(node.Left, i+1)
        if i == level {
            nums = append(nums, node.Val)
        }
        dfs(node.Right, i+1)
    }

    dfs(root, 0)
    if len(nums) == 0 {
        return -1
    }
    return nums[len(nums)/2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function levelMedian(root: TreeNode | null, level: number): number {
    const nums: number[] = [];

    const dfs = (node: TreeNode | null, i: number): void => {
        if (node === null) {
            return;
        }
        dfs(node.left, i + 1);
        if (i === level) {
            nums.push(node.val);
        }
        dfs(node.right, i + 1);
    };

    dfs(root, 0);
    if (nums.length === 0) {
        return -1;
    }
    return nums[nums.length >> 1];
}

评论