Minimum Absolute Difference in BST-K6K4.com

原题： https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/

题意： 给定一棵BST（二叉搜索树），节点值为非负整数，计算任意两节点差的绝对值的最小值。

约定：（1）BST中至少存在两个节点。

例子：

Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

标签： bst、difference、minimum、absolute、绝对值、面试

猜你感兴趣的圈子：

LeetCode交流圈

SLPH

2017-08-12 15:49:07 1楼#1层

Python中序遍历法：

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.last = -0x80000000
        self.ans = 0x7FFFFFFF
        def inOrderTraverse(root):
            if not root: return
            inOrderTraverse(root.left)
            self.ans = min(self.ans, root.val - self.last)
            self.last = root.val
            inOrderTraverse(root.right)
        inOrderTraverse(root)
        return self.ans

SLPH

2017-08-12 15:49:30 2楼#1层

Python递归法：

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        left, right = root.left, root.right
        ans = 0x7FFFFFFF
        if left:
            while left.right: left = left.right
            ans = min(root.val - left.val, self.getMinimumDifference(root.left))
        if right:
            while right.left: right = right.left
            ans = min(ans, right.val - root.val, self.getMinimumDifference(root.right))
        return ans

SLPH

2017-08-12 15:50:36 3楼#1层

C++中序遍历法：

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX, pre = -1;
        inorder(root, pre, res);
        return res;
    }
    void inorder(TreeNode* root, int& pre, int& res) {
        if (!root) return;
        inorder(root->left, pre, res);
        if (pre != -1) res = min(res, root->val - pre);
        pre = root->val;
        inorder(root->right, pre, res);
    }
};

SLPH

2017-08-12 15:51:00 4楼#1层

C++先序遍历法：

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX;
        helper(root, INT_MIN, INT_MAX, res);
        return res;
    }
    void helper(TreeNode* root, int low, int high, int& res) {
        if (!root) return;
        if (low != INT_MIN) res = min(res, root->val - low);
        if (high != INT_MAX) res = min(res, high - root->val);
        helper(root->left, low, root->val, res);
        helper(root->right, root->val, high, res);
    }
};

SLPH

2017-08-12 15:51:20 5楼#1层

C++迭代法：

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX, pre = -1;
        stack<TreeNode*> st;
        TreeNode *p = root;
        while (p || !st.empty()) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            p = st.top(); st.pop();
            if (pre != -1) res = min(res, p->val - pre);
            pre = p->val;
            p = p->right;
        }
        return res;
    }
};

取消

回复

推荐圈子

LeetCode交流圈