首页 > 试题广场 >

二叉搜索树最小差值

[编程题]二叉搜索树最小差值
  • 热度指数：1124 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。

数据范围：二叉树节点数满足 ，二叉树的节点值满足 ，保证每个节点的值都不同
示例1

输入

{2,1,3,#,#,#,4}

输出

1
示例2

输入

{3,1,5,#,#,#,9}

输出

2

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C++
牛娃牛娃头像 牛娃牛娃 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    vector<int> vec;
    //中序遍历  左--中--右  得到的就是 中减去左  右减去中
    void traversal(TreeNode*root){
        if(root ==nullptr)return ;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
        
    }
    
    int minDifference(TreeNode* root) {
        // write code here
        vec.clear();
        traversal(root);
        int res =INT_MAX;
        for(int i=1;i<vec.size();i++){
            res =min(res,vec[i]-vec[i-1]);
        }
        return res;
    }
};

发表于 2022-04-13 20:05:54 回复(0)
Java
牛客276339250号头像 牛客276339250号
遍历节点值，放在list中，遍历list查找出list差值最小的数据
import java.util.*;

/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int minNum = Integer.MAX_VALUE;
public int minDifference (TreeNode root) {
// write code here
List<Integer> lsit = new ArrayList<>();
mins(root,lsit);
for(int i=1;i<lsit.size();i++){
minNum = Math.min(Math.abs(lsit.get(i) - lsit.get(i-1)), minNum);
}
return minNum;
}
public void mins(TreeNode root, List<Integer> lsit) {
if (root == null) {
return;
}
lsit.add(root.val);
mins(root.left, lsit);
mins(root.right, lsit);
}
}
发表于 2023-11-28 16:08:18 回复(0)
C++
一品统合头像 一品统合
  • 对于二叉搜索树中任意节点，都有左子树节点的值 < 根节点的值 < 右子树节点的值。
  • 二叉搜索树的中序遍历序列就是所有节点非降序排列的结果，而任意两个节点之差的最小值一定诞生于两个相邻节点之间。
  • 因此，中序遍历并比较维护相邻两个节点之差的最小值即可。 
class Solution {
public:
    /**
     * 二叉搜索树中任意节点，都有左子树节点的值 < 根节点的值 < 右子树节点的值
     * 二叉搜索树的中序遍历序列就是所有节点非降序排列的结果，而任意节点的最小值
     * 一定诞生于两个相邻节点之间。因此，中序遍历并比较维护相邻两个节点之差的最小值
     * 即可。
     * @param root TreeNode类 
     * @return int整型
     */
    int minDifference(TreeNode* root) {
        stack<TreeNode*> s;
        int pre = -1000000000;
        int curr = 1000000000;
        int res = curr - pre;
        while (!s.empty() || root) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            // 计算中序遍历序列，相邻两个节点值的差
            curr = root->val;
            res = min(res, curr - pre);
            pre = curr;
            // 继续中序遍历
            root = root->right;
        }

        return res;
    }
};


发表于 2023-05-13 23:44:35 回复(0)
Python3
danspace头像 danspace 
class Solution:
    def minDifference(self , root: TreeNode) -> int:
        # write code here
        l = []
        def inOrder(root):
            if not root:
                return
            inOrder(root.left)
            l.append(root.val)
            inOrder(root.right)
        inOrder(root)
        ans = float('inf')
        for i in range(1, len(l)):
            ans = min(ans, l[i] - l[i-1])
        return ans

发表于 2023-04-27 16:30:17 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
//import "fmt"
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
*/
func minDifference( root *TreeNode ) int {
    arr:=[]int{}
    var order func(*TreeNode)
    order=func(root *TreeNode){
        if root==nil{
            return
        }
        order(root.Left)
        arr=append(arr,root.Val)
        order(root.Right)
    }
    order(root)
    ans:=arr[1]-arr[0]
    for i:=1;i<len(arr)-1;i++{
        tmp:=arr[i+1]-arr[i]
        if tmp<ans{
            ans=tmp
        }
    }
    return ans
}

发表于 2023-03-09 08:30:01 回复(0)
C
猪猪侠新新酱头像 猪猪侠新新酱 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型
 */
int preorder(struct TreeNode* root, int* arr) {
    static int count = 0;
    if (NULL != root) {
        arr[count++] = root->val;
        preorder(root->left, arr);
        preorder(root->right, arr);
    }
    return count;
}
int cnp(const void* e1,const void *e2){
    return *(int*)e1-*(int*)e2;
}
int minDifference(struct TreeNode* root ) {
    // write code here
    int* arr=(int *)malloc(sizeof(int)*100000);
    int count=preorder(root, arr);
    qsort(arr,count,sizeof(int),cnp);
    int ans=1000000000;
    for(int i=1;i<count;i++){
          if(ans>(arr[i]-arr[i-1]))
              ans=arr[i]-arr[i-1];
    }
    return ans;
}

发表于 2023-01-10 16:35:29 回复(0)
Python 3
大海里捞offer头像 大海里捞offer
思路也是中序遍历 但是超时了。
class Solution:
    def inorderTravseral(self,root):
        if not root:
            return []
        return self.inorderTravseral(root.left) + [root.val] + self.inorderTravseral(root.right)
    
    def minDifference(self , root: TreeNode) -> int:
        re = self.inorderTravseral(root)
        ans = float('inf')
        for i in range(len(re)-2):
            ans = min(ans, re[i+1] - re[i])
        return ans
       
发表于 2022-07-02 20:29:59 回复(1)
C++
牛客487629784号头像 牛客487629784号 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int minDifference(TreeNode* root) {
        // write code here
        //用中序遍历得到最小值
        help(root);
        return minn;
    }
    void help(TreeNode* root)
    {
        if(!root)
        {
            return;
        }
        help(root->left);
        minn=min(minn,abs(cur-root->val));
        cur=root->val;
        help(root->right);
    }
private:
    int cur=-999999;
    int minn=999999;
};
发表于 2022-07-01 10:15:56 回复(0)
Python2
菜鸡升职记头像 菜鸡升职记 
# -*- coding: utf-8 -*-


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class BT(object):
    def __init__(self):
        self.root = None

    def levelOrderToBT(self, nums):
        n = len(nums)

        if n > 0:
            self.root = TreeNode(nums[0])
            queue, idx = [self.root], 1
            while queue and idx < n:
                node = queue.pop(0)
                node.left = TreeNode(nums[idx]) if nums[idx] != None else None
                if node.left:
                    queue.append(node.left)
                node.right = TreeNode(nums[idx + 1]) \
                    if idx + 1 < n and nums[idx + 1] != None else None
                if node.right:
                    queue.append(node.right)
                idx += 2
        return self.root

    @staticmethod
    def levelOrder(root):
        if not root:
            return []

        queue, res = [root], []
        while queue:
            node = queue.pop(0)
            if node:
                res.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append(None)
        while res and res[-1] == None:
            res.pop()

        return res


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f8ac976b49bd450887b9281f315186c7?tpId=196&tqId=40504&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    算法：
        中序遍历二叉树，使用self.pre记录当前节点的前驱节点的val，不断更新差值diff与self.pre
    复杂度：
        时间复杂度：O(N)，N为节点数
        空间复杂度：O(H), H为树的高度
    """

    def minDifference(self, root):
        # write code here
        def inOrder(root):
            if root:
                inOrder(root.left)
                if self.pre == -1:
                    self.pre = root.val
                else:
                    self.diff = min(self.diff, abs(root.val - self.pre))
                    self.pre = root.val
                inOrder(root.right)

        self.diff, self.pre = 10 ** 9, -1

        inOrder(root)

        return self.diff


if __name__ == "__main__":
    sol = Solution()

    nums = [2, 1, 3, None, None, None, 4]

    # nums = [3, 1, 5, None, None, None, 9]

    # nums = [9, 4, 16, 1, 7, 11, 19]

    bt = BT()
    bt1 = bt.levelOrderToBT(nums)
    # print BT.levelOrder(bt1)

    res = sol.minDifference(bt1)
    print res

发表于 2022-06-23 15:48:17 回复(0)
Java
世界杯2009头像 世界杯2009 
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int minDifference(TreeNode root) {
        // write code here
        if (root == null) {
            return -1;
        }
        return getMin(root);
    }

    private int getMin(TreeNode root) {
        if (root.left != null && root.right != null) {
            return Math.min(Math.min(root.val - root.left.val, root.right.val - root.val),
                Math.min(getMin(root.right), getMin(root.left)));
        } else if (root.left != null) {
            return Math.min(root.val - root.left.val, getMin(root.left));
        } else if (root.right != null) {
            return Math.min(root.right.val - root.val, getMin(root.right));
        } else {
            return Integer.MAX_VALUE;
        }
    }
}

发表于 2022-03-27 21:47:20 回复(0)
提交观点

问题信息

树 dfs 广度优先搜索(BFS)
难度：
10条回答 2616浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号