【LeetCode】二叉搜索树节点最小距离 Java 题解

HQ数字卡

关注

发布于: 2021 年 04 月 13 日

题目介绍

给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。

示例 1：

输入：root = [4,2,6,1,3]

输出：1

思路

这是一个关于树的题目，二叉搜索数的重要特征是中序遍历是升序。利用这个特征，可以得到答案。

代码

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *         this.val = val; *         this.left = left; *         this.right = right; *     } * } */class Solution {    List<Integer> list = new ArrayList<>();    public int minDiffInBST(TreeNode root) {        int ans = Integer.MAX_VALUE;        inOrder(root);                for (int i = 1; i < list.size(); i++) {            ans = Math.min(ans, list.get(i) - list.get(i - 1));        }        return ans;    }
    public void inOrder(TreeNode root) {        if (root == null) {            return;        }        if (root.left != null) {            inOrder(root.left);        }        int val = root.val;        list.add(val);        if (root.right != null) {            inOrder(root.right);        }    }}

复制代码

总结

上述算法的时间复杂度 O(n), 空间复杂度是 O(n)。
此题复习了搜索二叉树的性质。坚持每日一题，加油！

发布于: 2021 年 04 月 13 日阅读数: 13

原文链接:【http://xie.infoq.cn/article/c6b898cdf396fbfd7d2f75d47】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】二叉搜索树节点最小距离 Java 题解

题目介绍

思路

代码

总结

HQ数字卡

评论