leetcode-17-BST

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;

    }

巴特西

leetcode-17-BST

最新文章

热门文章