Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]

Output: 1

Explanation:

Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4

        /   \

      2      6

     / \

    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

The size of the BST will be between 2 and 100.
The BST is always valid, each node's value is an integer, and each node's value is different.

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def minDiffInBST(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        # traverse node from min to max

        self.last_node = None

        self.min_diff = float('inf')

        def dfs(node):

            if not node: return

            dfs(node.left)

            if self.last_node:

                self.min_diff = min(self.min_diff, node.val-self.last_node.val)

            self.last_node = node

            dfs(node.right)

        dfs(root)

        return self.min_diff

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def minDiffInBST(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        # traverse node from min to max

        last_node = None

        ans = float("inf")

        node = root

        stack = []

        while node:

            stack.append(node)

            node = node.left

        while stack:

            node = stack.pop()

            if last_node:

                ans = min(ans, node.val-last_node.val)

            last_node = node

            node = node.right

            while node:

                stack.append(node)

                node = node.left

        return ans

Morris Traversal:

# Definition for a binary tree node.

# class TreeNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution(object):

    def minDiffInBST(self, root):

        """

        :type root: TreeNode

        :rtype: int

        """

        # traverse node from min to max

        last_node = None

        ans = float("inf")

        cur = root

        while cur:

            if cur.left is None:

                if last_node:

                    ans = min(ans, cur.val-last_node.val)

                last_node = cur

                cur = cur.right

            else:

                tmp = cur.left

                while tmp.right and not (tmp.right is cur):

                    tmp = tmp.right

                if not tmp.right:

                    tmp.right = cur

                    cur = cur.left

                else:

                    tmp.right = None

                    if last_node:

                        ans = min(ans, cur.val-last_node.val)

                    last_node = cur

                    cur = cur.right

        return ans

巴特西

leetcode 783. Minimum Distance Between BST Nodes 以及同样的题目 530. Minimum Absolute Difference in BST

Morris Traversal:

最新文章

热门文章