关注Java领域相关技术 记录有趣的事情

binary search tree

LeetCode-530. 二叉搜索树的最小绝对差

问题地址 LeetCode每日一题/2020-10-12 LeetCode530. 二叉搜索树的最小绝对差 问题描述 规则 给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。 示例 示例1 输入: 1 \ 3 / 2 输出:1 解释 最小绝对差为 1,其中 2 和 1 的差的绝对值为 1(或者 2 和 3)。 提示: 树中至少有 2 个节点。 本题与 783 相同 解析 解题思路 我们都知道二叉搜索树左子树不大于根节点,右子树不小于根节点。我们采用中序遍历的处理这个问题; 方法一:先利用一次中序遍历将值保存在一个数组中再进行遍历求解; 方法二:在中序遍历的过程中…
US-B.Ralph
4 months ago

LeetCode-235. 二叉搜索树的最近公共祖先

问题地址 LeetCode每日一题/2020-09-27 LeetCode235. 二叉搜索树的最近公共祖先 问题描述 规则 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科 中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉搜索树:  root =  示例 示例一: 输入: root = , p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例二: 输入: root = , p …
US-B.Ralph
5 months ago

LeetCode-501. 二叉搜索树中的众数

问题地址 LeetCode每日一题/2020-09-24 LeetCode501. 二叉搜索树中的众数 问题描述 规则 给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。 假定 BST 有如下定义: 结点左子树中所含结点的值小于等于当前结点的值 结点右子树中所含结点的值大于等于当前结点的值 左子树和右子树都是二叉搜索树 示例 示例一: 给定 BST , 1 \ 2 / 2 返回. 提示: 如果众数超过1个,不需考虑输出顺序 进阶 你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内) 解析 解题思路 这个题目最直观的做法是遍历的时候使…
US-B.Ralph
5 months ago

LeetCode-538. 把二叉搜索树转换为累加树

问题地址 LeetCode每日一题/2020-09-21 LeetCode538. 把二叉搜索树转换为累加树 问题描述 规则 给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 注意 本题(https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ "力和 1038") 相同。 示例 示例一: 输入: 原始二叉搜索树: 5 / \ 2 13 输出: 转换为累加树: 18 / \ 20 13 解析…
US-B.Ralph
5 months ago

LeetCode-109. 有序链表转换二叉搜索树

问题地址 LeetCode每日一题/2020-08-18 LeetCode109. 有序链表转换二叉搜索树 问题描述 规则 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 示例1 给定的有序链表: , 一个可能的答案是:, 它可以表示下面这个高度平衡二叉搜索树: 0 / \ -3 9 / / -10 5 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode …
US-B.Ralph
6 months ago