-
二叉樹中第二小的節點
給定一個非空特殊的二叉樹，每個節點都是正數，并且每個節點的子節點數量隻能為 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)
/**
* 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 findSecondMinimumValue(TreeNode* root) {
return dfs(root);
}
int dfs(TreeNode* root) {
if (root == nullptr || root->left == nullptr) return -1; //若沒有節點則不存在第二小的數
if (root->left->val == root->right->val) { //兩子節點值相等，遞歸傳回兩子節點各第二小的值，并取其最小值
if (dfs(root->left) == -1) return dfs(root->right); //注意傳回值-1，
if (dfs(root->right) == -1) return dfs(root->left);
return min(dfs(root->left), dfs(root->right));
}
if (root->val == root->left->val){//除了以上情況之外的簡單判斷，
if (dfs(root->left) == -1) return root->right->val;
return min(root->right->val, dfs(root->left));
} else {
if (dfs(root->right)== -1) return root->left->val;
return min(root->left->val, dfs(root->right));
}
}
};