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

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

Category	Difficulty	Likes	Dislikes
algorithms	Easy (48.27%)	265	-

Tags
Companies
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 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 <= 231 - 1
• 对于树中每个节点 root.val == min(root.left.val, root.right.val)

---

Discussion | Solution

思路

(1)
(3-1)
(3-4) (2-1)
可以易理解，根节点一定是最小的节点。通过 dfs，分别遍历左右节点，找到第一个严格大于根节点的节点，并记录下来，提前剪枝（将该节点看为一颗单独的新树，可以得到这个节点一定是新树的最小节点，所以剩余节点都不需要进行判断，直接返回即可）。例如上图在根节点的左子树找到了 3，更新 res，再去深度遍历右子树找到第一个比 res 小且比根节点大的数。最后返回 res 即可。

解答

/*
 * @lc app=leetcode.cn id=671 lang=javascript
 *
 * [671] 二叉树中第二小的节点
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findSecondMinimumValue = function (root) {
  let res = -1;

  const dfs = (node) => {
    if (!node) return;
    if (res !== -1 && node.val >= res) {
      return;
    }
    if (node.val > root.val) {
      res = node.val;
      return;
    }
    dfs(node.left);
    dfs(node.right);
  };

  dfs(root);

  return res;
};
// @lc code=end