LeetCode-二叉树中第二小的节点

Author： yfx
发布时间：July 27, 2021
563 views
No comments
3247 words
Categories：算法 C/C++ Python

# Problem - [二叉树中第二小的节点](https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/)

> **分析：**
>
> 若一个结点有两个子节点那么该结点的值为两个子节点中较小的一个。
>
> **算法：**
>
> 故可以得到根节点为树中值最小的结点。此时需要找到第二小的结点，我们可以选择`DFS`或者`BFS`去遍历整个树即可得到第二小值。
>
> **细节：**
>
> 定义`ans`为`-1`，在搜索当中若当前`ans`不为`-1`那么如果该结点值比`ans`大则直接退出否则若比根节点大则更新`ans`，最后返回`ans`即可。

## 方法一： DFS

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-c99a20cece00a08d6b88201810fb80b0920' role="tab" data-target='#tabs-c99a20cece00a08d6b88201810fb80b0920'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-01e0b0a61e007db3933f983f9eb7ca41331' role="tab" data-target='#tabs-01e0b0a61e007db3933f983f9eb7ca41331'>**Python 3**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-e95a65d27b1edf6692e90575c0e0eebe532' role="tab" data-target='#tabs-e95a65d27b1edf6692e90575c0e0eebe532'>**C++新语法学习**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-c99a20cece00a08d6b88201810fb80b0920' class="tab-pane fade active in">

```cpp
class Solution {
    int ans, rootvalue;
    void dfs(TreeNode* node) {
        if (!node) return;
        if (ans != -1 && node -> val >= ans) return;
        if (node -> val > rootvalue) ans = node -> val;
        dfs(node -> left);
        dfs(node -> right);
    }
public:
    int findSecondMinimumValue(TreeNode* root) {
        ans = -1; rootvalue = root -> val;
        dfs(root);
        return ans;
    }
};
```

</div><div role="tabpanel" id='tabs-01e0b0a61e007db3933f983f9eb7ca41331' class="tab-pane fade  ">

```python
class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        ans, rootvalue = -1, root.val

def dfs(node : TreeNode) -> None:
            nonlocal ans
            if not node:
                return
            if ans != -1 and node.val > ans:
                return
            if node.val > rootvalue:
                ans = node.val
            dfs(node.left)
            dfs(node.right)

dfs(root)
  
        return ans
```

~~ps：`nolocal`该[关键字](https://blog.csdn.net/qq_42780289/article/details/89244761)是外部嵌套函数内的变量~~

</div><div role="tabpanel" id='tabs-e95a65d27b1edf6692e90575c0e0eebe532' class="tab-pane fade  ">

```cpp
class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        int rootvalue = root -> val;

function<void(TreeNode*)> dfs = [&](TreeNode* node) {
            if (!node) return;
            if (ans != -1 && node->val >= ans) return;
            if (node->val > rootvalue) ans = node->val;
            dfs(node->left); dfs(node->right);
        };

dfs(root);
        return ans;
    }
};
```

~~ps：函数内嵌套lambda函数~~

</div>
</div>
</div>

---

## 方法二：BFS

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-718a9d925cff7c74b764597f2aae7e94600' role="tab" data-target='#tabs-718a9d925cff7c74b764597f2aae7e94600'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-ffacafd92cef829a5c8dce060dc148f1911' role="tab" data-target='#tabs-ffacafd92cef829a5c8dce060dc148f1911'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-718a9d925cff7c74b764597f2aae7e94600' class="tab-pane fade active in">

```cpp
class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        int rootvalue = root -> val;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            auto node = q.front(); q.pop();
            if (!node) continue;
            if (ans != -1 && node -> val >= ans) continue;
            if (node -> val > rootvalue) ans = node -> val;
            q.push(node -> left); q.push(node -> right);
        }
        return ans;
    }
};
```

</div><div role="tabpanel" id='tabs-ffacafd92cef829a5c8dce060dc148f1911' class="tab-pane fade  ">

```python
class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        ans, rootvalue = -1, root.val
        q = deque([root])

while q:
            node = q.popleft()
            if not node: continue
            if ans != -1 and node.val >= ans: continue
            if node.val > rootvalue:ans = node.val
            q.append(node.left); q.append(node.right)
  
        return ans
```

~~ps：python版的队列学习了~~

</div>
</div>
</div>

Last modification：August 18, 2021

看着给点？(●'◡'●)？

LeetCode-二叉树中第二小的节点

yfx • 2021 年 07 月 27 日

# Problem - [二叉树中第二小的节点](https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/)

## 方法一： DFS

</div><div role="tabpanel" id='tabs-01e0b0a61e007db3933f983f9eb7ca41331' class="tab-pane fade  ">

```python
class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        ans, rootvalue = -1, root.val

dfs(root)
  
        return ans
```

~~ps：`nolocal`该[关键字](https://blog.csdn.net/qq_42780289/article/details/89244761)是外部嵌套函数内的变量~~

</div><div role="tabpanel" id='tabs-e95a65d27b1edf6692e90575c0e0eebe532' class="tab-pane fade  ">

```cpp
class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        int ans = -1;
        int rootvalue = root -> val;

dfs(root);
        return ans;
    }
};
```

~~ps：函数内嵌套lambda函数~~

</div>
</div>
</div>

---

## 方法二：BFS

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-718a9d925cff7c74b764597f2aae7e94600' role="tab" data-target='#tabs-718a9d925cff7c74b764597f2aae7e94600'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-ffacafd92cef829a5c8dce060dc148f1911' role="tab" data-target='#tabs-ffacafd92cef829a5c8dce060dc148f1911'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-718a9d925cff7c74b764597f2aae7e94600' class="tab-pane fade active in">

</div><div role="tabpanel" id='tabs-ffacafd92cef829a5c8dce060dc148f1911' class="tab-pane fade  ">

```python
class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        ans, rootvalue = -1, root.val
        q = deque([root])

~~ps：python版的队列学习了~~

</div>
</div>
</div>

LeetCode-二叉树中第二小的节点

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

本站Handsoem主题的美化教程

宝塔网站nginx反向代理避坑

纪元1800.DLC完全解锁补丁【正版适用】-2023.11.14

LeetCode-高效制胜-两数之和

LeetCode-高效制胜-两数之和 II - 输入有序数组

GitHub避坑

LeetCode-高效制胜-两数之和

LeetCode-第253场周赛

Python相关函数语法例题

LeetCode-第372场周赛

LeetCode-二叉树中第二小的节点

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

LeetCode-二叉树中第二小的节点

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款