[LeetCode]Second Minimum Node In a Binary Tree

很典型的递归思路的题，对于当前节点，我们有以下几种情况：

• 当前节点有左右节点
• 左子节点left大于右子节点right，那么left有可能是second minimum，但是右子树当中有可能有比 left更小比right大的值，所以我们要去右子树当中找second minimum然后和left比较
• 右子节点right大于左子节点left，同理
• 右子节点right和左子节点left相等，这个时候这两个都不可能是当前tree的second minimum，所以我们要去各自的子树去找然后比较
• 当前节点没有左右节点
• 我们找不到以当前节点为root的second minimum，return -1

时间复杂度O(n)，空间复杂度O(log n)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int findSecondMinimumValue(TreeNode* root) {
	if(!root)return -1;
	if(root->left)
	{
	int left = root->left->val > root->right->val? root->left->val: findSecondMinimumValue(root->left);
	int right = root->left->val < root->right->val? root->right->val: findSecondMinimumValue(root->right);
	return left == -1? right: (right == -1? left: min(left, right));
	}
	return -1;
	}
	};

view raw Second Minimum Node In a Binary Tree.cpp hosted with ❤ by GitHub