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

binary tree

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

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

LeetCode-257. 二叉树的所有路径

问题地址 LeetCode每日一题/2020-09-04 LeetCode257. 二叉树的所有路径 问题描述 规则 给定一个二叉树,返回所有从根节点到叶子节点的路径。 说明: 叶子节点是指没有子节点的节点。 示例1 输入: 1 / \ 2 3 \ 5 输出: 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3 解析 解题思路 首先想到的方法是深度优先搜索。树节点分两种,叶子节点、非叶子节点,根据不同的节点类型,采用不同的处理方法: 如果当前节点是叶子节点: 将当前节点添加到当前路径末尾; 将得到的一条从根节点到叶子节点的路径,加入到答案; 如果当前节点不是叶…
US-B.Ralph
8 months ago