530. Minimum Absolute Difference in BST
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
解题思路：
先序遍历，存下来，然后排序，找临近两个的最小差值。
效率不高。。。后面再想想怎么改进？？？
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
get(root);
sort(nodes.begin(), nodes.end());
int Mini = abs(nodes[0]-nodes[1]);
for (int i = 1; i < nodes.size(); i++) {
Mini = min(Mini, abs(nodes[i]-nodes[i-1]));
}
return Mini;
}
void get(TreeNode* root) {
if (root)
nodes.push_back(root->val);
if (root->left)
get(root->left);
if (root->right)
get(root->right);
}
private:
vector<int> nodes;
};
235. Lowest Common Ancestor of a Binary Search Tree
解题思路：
直接找。。如果p,q的值大于root，就到右子树找；如果都小于root，就到左子树找，否则返回root。
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left, p, q);
if (p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right, p, q);
return root;
}