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

中序遍历

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

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

LeetCode-145. 二叉树的后序遍历

问题地址 LeetCode每日一题/2020-09-29 LeetCode145. 二叉树的后序遍历 问题描述 规则 给定一个二叉树,返回它的 *后序 遍历。 示例 输入: 1 \ 2 / 3 输出: 进阶 递归算法很简单,你可以通过迭代算法完成吗? 解析 解题思路 后序遍历:是按照访问左右根的顺序遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。整个遍历过程天然具有递归的性质。 递归遍历树的时候隐式的维护一个栈,我们使用迭代的方法遍历树,需要自己维护栈; 下面介绍一种方法标记法,针对树的前、中、后序遍历可以写统一模板的代码; 在使用栈时,无法同时处理访问节…
US-B.Ralph
2 years ago

LeetCode-106. 从中序与后序遍历序列构造二叉树

问题地址 LeetCode每日一题/2020-09-25 LeetCode106. 从中序与后序遍历序列构造二叉树 问题描述 规则 根据一棵树的中序遍历与后序遍历构造二叉树。 注意 你可以假设树中没有重复的元素。 示例 示例一: 给出 中序遍历 inorder = 后序遍历 postorder = 返回二叉树 3 / \ 9 20 / \ 15 7 解析 解题思路 题目给定一个二叉树的中序遍历序列、后序遍历序列,且二叉树中元素没有重复; 根据后序遍历序列常用算法,可以看到后序遍历序列的最后一个元素处理的是根节点。 if (root == null) return; postorderTrave…
US-B.Ralph
2 years ago

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

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

LeetCode-617. 合并二叉树

问题地址 LeetCode每日一题/2020-09-23 LeetCode617. 合并二叉树 问题描述 规则 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。 示例 示例一: 输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7 注意 合并必须从两个树的根节点开始。 解析 解题思路 题目要…
US-B.Ralph
2 years 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
2 years ago

LeetCode-94. 二叉树的中序遍历

问题地址 LeetCode每日一题/2020-09-14 LeetCode94. 二叉树的中序遍历 问题描述 规则 给定一个二叉树,返回它的中序 遍历。 示例 示例: 输入: 1 \ 2 / 3 输出: 进阶 递归算法很简单,你可以通过迭代算法完成吗? 解析 解题思路 递归 二叉树的中序遍历:按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。因此整个遍历过程天然具有递归的性质,我们可以直接用递归函数来模拟这一过程。 数据操作分析 根据中序遍历的定义只需要遍历左子树、root、右子树即可 遍历的终止条件是 root==nu…
US-B.Ralph
2 years ago