671. 二叉树中第二小的节点

🟢 🔖 树 深度优先搜索 二叉树 🔗 力扣open in new window LeetCodeopen in new window

题目

Given a non-empty special binary tree consisting of nodes with the non- negative value, where each node in this tree has exactly two or zero sub- node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

Constraints:

The number of nodes in the tree is in the range [1, 25].
1 <= Node.val <= 2^31 - 1
root.val == min(root.left.val, root.right.val) for each internal node of the tree.

题目大意

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。

更正式地说，即 root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树，你需要输出所有节点中的 第二小的值 。

如果第二小的值不存在的话，输出 -1 。

示例 1：

输入： root = [2,2,5,null,null,5,7]
输出： 5
解释： 最小的值是 2 ，第二小的值是 5 。

示例 2：

输入： root = [2,2,2]
输出： -1
解释： 最小的值是 2, 但是不存在第二小的值。

提示：

树中节点数目在范围 [1, 25] 内
1 <= Node.val <= 2^31 - 1
对于树中每个节点 root.val == min(root.left.val, root.right.val)

解题思路

根节点的值：根据题意，二叉树的根节点的值是最小的节点值，我们需要寻找大于根节点值的第二小节点。
深度优先搜索（DFS）：使用深度优先搜索（DFS）从根节点开始遍历树，递归地查找树的左子树和右子树。在递归过程中，保持跟踪找到的比根节点大的最小值。
遍历逻辑：
- 如果当前节点值大于 min，返回该节点的值，因为它可能是第二小的节点。
- 否则，递归地检查当前节点的左子树和右子树。
- 对于每个子树，递归返回两个子树中较小的有效结果。
返回第二小值：
- 如果在整个树中找到了比根节点值大的节点，返回第二小的节点值。
- 如果没有找到比根节点大的节点，返回 -1。

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树中节点的总数，需要遍历树中的每个节点一次。
空间复杂度：O(h)，其中 h 是树的高度。
- 由于递归需要栈空间，最坏情况下是树的高度为 n，此时空间复杂度为 O(n)；
- 最好情况下是树是完全平衡的，空间复杂度为 O(log n)。

代码

var findSecondMinimumValue = function (root) {
	let min = root.val;

	// 深度优先搜索递归函数
	const dfs = (node) => {
		if (!node) return -1; // 如果节点为空，返回-1

		// 如果当前节点的值大于根节点的值，可能是第二小值
		if (node.val > min) return node.val;

		// 递归遍历左子树和右子树
		const left = dfs(node.left);
		const right = dfs(node.right);

		// 如果左子树或右子树为空，则返回另一个子树的值
		if (left == -1 || right == -1) return Math.max(left, right);

		// 返回左子树和右子树中的较小值
		return Math.min(left, right);
	};

	return dfs(root); // 从根节点开始递归查找
};

671. 二叉树中第二小的节点

# 671. 二叉树中第二小的节点

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

671. 二叉树中第二小的节点

题目

题目大意

解题思路

复杂度分析

代码

相关题目