我要招人

去企业版

首页 > 试题广场 >

二叉搜索树最小差值

[编程题]二叉搜索树最小差值

热度指数：1131 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一棵二叉搜索树，请你返回树中任意两节点之差的最小值。

数据范围：二叉树节点数满足 $2 \le n \le 10^5 \$ ，二叉树的节点值满足 $0 \le val \le 10^9 \$ ，保证每个节点的值都不同

示例1

输入

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

输出

示例2

输入

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

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

牛客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)

Java

世界杯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)