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

tree

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
9 months ago

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

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

LeetCode-834. 树中距离之和

问题地址 LeetCode每日一题/2020-10-06 LeetCode834. 树中距离之和 问题描述 规则 给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。 第 i 条边连接节点 edges 和 edges 。 返回一个表示节点 i 与其他所有节点距离之和的列表 ans。 示例 示例1 输入: N = 6, edges = ,,,,] 输出: 解释: 如下为给定的树的示意图: 0 / \ 1 2 /|\ 3 4 5 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) …
US-B.Ralph
9 months 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
9 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
9 months 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
9 months ago

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

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

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

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

LeetCode-404. 左叶子之和

问题地址 LeetCode每日一题/2020-09-19 LeetCode404. 左叶子之和 问题描述 规则 计算给定二叉树的所有左叶子之和。 示例 示例1 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 解析 解题思路 左叶子的判定条件 它是某个节点的左子节点; 它是一个叶子结点; 因此我们遍历整棵树,当我们遍历到某个节点 $\textit{node}$ 时,如果它的左子节点是一个叶子结点,那么就将它的左子节点的值累加计入答案。 数据操作分析 遍历整棵树,在遍历的过程中,判定某个节点是否满足左叶子的条件,判断条件: 左子节点; 叶…
US-B.Ralph
10 months ago