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

二叉树

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

问题地址 LeetCode每日一题/2020-10-15 LeetCode116. 填充每个节点的下一个右侧节点指针 问题描述 规则 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 NULL。 进阶 你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归…
US-B.Ralph
a year ago

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

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

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

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

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

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

LeetCode-968. 监控二叉树

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

LeetCode-78. 子集

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

LeetCode-107. 二叉树的层次遍历 II

问题地址 LeetCode每日一题/2020-09-06 LeetCode107. 二叉树的层次遍历 II 问题描述 规则 给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 例如: 给定二叉树 , 3 / \ 9 20 / \ 15 7 返回其自底向上的层次遍历为: , , ] 解析 解题思路 使用递归逐层遍历; 当前节点为空则直接返回; 当前节点无子节点时直接返回; 遍历过程中,使用map存储每一层的元素,key为深度,value为当前深度的所有元素; 数据操作分析 复杂度分析 时间复杂度,$O(N^2)$,其中 N 表示节点数目。…
US-B.Ralph
a year ago