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

LeetCode

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

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

LeetCode-117. 填充每个节点的下一个右侧节点指针 II

问题地址 LeetCode每日一题/2020-09-28 LeetCode117. 填充每个节点的下一个右侧节点指针 II 问题描述 规则 给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 进阶 你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。 示例 输入：root = …
1
US-B.Ralph
US-B.Ralph
2 years 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
US-B.Ralph
2 years ago

LeetCode-113. 路径总和 II

问题地址 LeetCode每日一题/2020-09-26 LeetCode113. 路径总和 II 问题描述 规则 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 注意 你可以假设树中没有重复的元素。 示例 示例一： 给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: , ] 解析 解题思路 从根节点开始遍历每一条路径，当遍历到叶子节点且该路径节点之和等于sum则将其添加到结果集中； 数据操作分析 遍历整棵树 当节点为空，直接返回； …
US-B.Ralph
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
US-B.Ralph
2 years ago

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

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

LeetCode-968. 监控二叉树

问题地址 LeetCode每日一题/2020-09-22 LeetCode968. 监控二叉树 问题描述 规则 给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 示例一： 输入： 输出：1 解释：如图所示，一台摄像头足以监控所有节点。 示例二： 输入： 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 提示 给定树的节点数的范围是 。 每个节点的值都是 0。 解析 解题思路 根据题意，我们给节点定义一些状态： 0：空白节点； 1：被监控节点； 2…
US-B.Ralph
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
US-B.Ralph
2 years ago

LeetCode-78. 子集

问题地址 LeetCode每日一题/2020-09-20 LeetCode78. 子集 问题描述 规则 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明 解集不能包含重复的子集。 示例 示例一： 输入: nums = 输出: ,   ,   ,   ,   ,   ,   ,   [] ] 解析 解题思路 每个元素都有两个选项，选择、不选择； 题目示例，元素1可以考虑选择或不选择，然后考察2，以此类推； 其递归树为： 一个子树就是一个递归调用，对当前枚举的数，选和不选可以分出两个分支，分别对应两个递归的子调用，在子调用中，考察下一个数。 当 inx 越界（in…
US-B.Ralph
US-B.Ralph
2 years ago