3831. Median of a Binary Search Tree Level 🔒

题目描述

You are given the root of a Binary Search Tree (BST) and an integer level.

The root node is at level 0. Each level represents the distance from the root.

Return the median value of all node values present at the given level. If the level does not exist or contains no nodes, return -1.

The median is defined as the middle element after sorting the values at that level in non-decreasing order. If the number of values at that level is even, return the upper median (the larger of the two middle elements after sorting).

Example 1:

Input: root = [4,null,5,null,7], level = 2

Output: 7

Explanation:

The nodes at level = 2 are [7]. The median value is 7.

Example 2:

Input: root = [6,3,8], level = 1

Output: 8

Explanation:

The nodes at level = 1 are [3, 8]. There are two possible median values, so the larger one 8 is the answer.

Example 3:

Input: root = [2,1], level = 2

Output: -1

Explanation:

There is no node present at level = 2, so the answer is -1.

Constraints:

The number of nodes in the tree is in the range [1, 2 * 10⁵].
1 <= Node.val <= 10⁶
0 <= level <= 2 * 10⁵

解法

方法一：DFS

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

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

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

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

Python3JavaC++GoTypeScript

# 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

/**
 * 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);
    }
}

/**
 * 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];
    }
};

/**
 * 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]
}

/**
 * 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];
}

3831. Median of a Binary Search Tree Level 🔒

题目描述

解法

方法一：DFS

评论