文章目录
🌈你好呀!我是 山顶风景独好
🎈欢迎踏入我的博客世界,能与您在此邂逅,真是缘分使然!😊
🌸愿您在此停留的每一刻,都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索,更是一个自由交流的平台,期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程,携手挖掘更多可能,共同进步!💪✨
117.【中等】填充每个节点的下一个右侧节点指针 II
给定一个二叉树:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
- 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。
- 初始状态下,所有 next 指针都被设置为 NULL 。
示例 1:
- 输入:root = [1,2,3,4,5,null,7]
- 输出:[1,#,2,3,#,4,5,7,#]
- 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),‘#’ 表示每层的末尾。
示例 2:
- 输入:root = []
- 输出:[]
class Solution {
// 连接二叉树的每一层
public Node connect(Node root) {
// 如果根节点为空,则直接返回null
if (root == null) {
return null;
}
// 创建一个队列用于层序遍历
Queue<Node> queue = new ArrayDeque<Node>();
// 将根节点加入队列
queue.offer(root);
// 当队列不为空时,说明还有节点需要处理
while (!queue.isEmpty()) {
// 获取当前层的节点数量
int n = queue.size();
// 初始化last为null,用于记录当前层的上一个节点
Node last = null;
// 遍历当前层的所有节点
for (int i = 1; i <= n; ++i) {
// 出队一个节点
Node f = queue.poll();
// 如果该节点的左子节点不为空,将其加入队列
if (f.left != null) {
queue.offer(f.left);
}
// 如果该节点的右子节点不为空,将其加入队列
if (f.right != null) {
queue.offer(f.right);
}
// 如果这不是当前层的第一个节点(即i != 1),则将上一个节点last的next指向当前节点f
if (i != 1) {
last.next = f;
}
// 更新last为当前节点f,以便处理下一个节点
last = f;
}
}
// 返回根节点,此时整棵树的每一层节点都已经连接好了
return root;
}
}
114.【中等】二叉树展开为链表
- 给你二叉树的根结点 root ,请你将它展开为一个单链表:
- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
- 示例 1:
- 输入:root = [1,2,5,3,4,null,6]
- 输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2:
- 输入:root = []
- 输出:[]
示例 3:
- 输入:root = [0]
- 输出:[0]
class Solution {
// 平展二叉树的方法,将二叉树转换为右子树链表的形式
public void flatten(TreeNode root) {
// 创建一个列表,用于存储前序遍历的结果
List<TreeNode> list = new ArrayList<TreeNode>();
// 对二叉树进行前序遍历,并将节点添加到列表中
preorderTraversal(root, list);
// 获取列表中节点的数量
int size = list.size();
// 从第二个节点开始遍历列表(索引从1开始,因为第一个节点已经是root了)
for (int i = 1; i < size; i++) {
// 获取前一个节点和当前节点
TreeNode prev = list.get(i - 1), curr = list.get(i);
// 将前一个节点的左子树设置为null(因为我们要平展树)
prev.left = null;
// 将前一个节点的右子树设置为当前节点,从而实现平展效果
prev.right = curr;
}
}
// 前序遍历二叉树的方法,将遍历到的节点添加到给定的列表中
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
// 如果当前节点不为null,则进行以下操作
if (root != null) {
// 将当前节点添加到列表中
list.add(root);
// 递归遍历左子树
preorderTraversal(root.left, list);
// 递归遍历右子树
preorderTraversal(root.right, list);
}
}
}
129.【中等】求根节点到叶节点数字之和
- 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:- 例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。- 叶节点 是指没有子节点的节点。
示例 1:
- 输入:root = [1,2,3]
- 输出:25
- 解释:
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此,数字总和 = 12 + 13 = 25
示例 2:
- 输入:root = [4,9,0,5,1]
- 输出:1026
- 解释:
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此,数字总和 = 495 + 491 + 40 = 1026
class Solution {
// 主方法,接收一个树的根节点,并返回所有从根到叶子节点的数字之和
public int sumNumbers(TreeNode root) {
return dfs(root, 0); // 调用深度优先搜索方法,初始和为0
}
// 深度优先搜索方法,递归地遍历树的每个节点
public int dfs(TreeNode root, int prevSum) {
if (root == null) { // 如果节点为空,则返回0
return 0;
}
// 计算当前路径上的数字之和,将前一个节点值的10倍加上当前节点的值
int sum = prevSum * 10 + root.val;
if (root.left == null && root.right == null) { // 如果当前节点是叶子节点
return sum; // 返回当前路径的数字之和
} else {
// 如果不是叶子节点,则递归地对左子树和右子树进行深度优先搜索,
// 并将两个子树的结果相加
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
}
124.【困难】二叉树中的最大路径和
- 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
- 路径和 是路径中各节点值的总和。
- 给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
- 输入:root = [1,2,3]
- 输出:6
- 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
- 输入:root = [-10,9,20,null,null,15,7]
- 输出:42
- 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int max = Integer.MIN_VALUE; // 初始化最大路径和为整数的最小值
public int maxPathSum(TreeNode root) {
// 调用递归函数计算包含根节点的最大路径和
containCurNodeMaxSum(root);
// 返回找到的最大路径和
return max;
}
private int containCurNodeMaxSum(TreeNode node) {
if (node == null) {
// 如果节点为空,返回0表示没有路径和
return 0;
}
// 递归计算左子树中包含左孩子节点的最大路径和
int leftMax = containCurNodeMaxSum(node.left);
// 递归计算右子树中包含右孩子节点的最大路径和
int rightMax = containCurNodeMaxSum(node.right);
// 计算当前节点为根节点的三种可能路径和的最大值:
// 1. 只包含当前节点值
// 2. 包含当前节点值和左子树中的最大路径和
// 3. 包含当前节点值和右子树中的最大路径和
int curMax = Math.max(Math.max(node.val + leftMax, node.val + rightMax), node.val);
// 更新全局最大路径和:
// 1. 可能是当前节点值加上左子树和右子树中的最大路径和(当左右子树都贡献正值时)
// 2. 可能是以当前节点为根的其他路径和(即curMax)
// 3. 可能是之前已经计算过的全局最大路径和
max = Math.max(Math.max(node.val + leftMax + rightMax, curMax), max);
// 返回以当前节点为根的最大路径和(注意:这里只返回了当前节点为根节点的三种可能路径和的最大值,
// 并没有包含左右子树同时贡献正值的情况,因为这种情况已经在更新全局最大路径和时考虑了)
return curMax;
}
}
173.【中等】二叉搜索树迭代器
实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器:
- BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字,且该数字小于 BST 中的任何元素。
- boolean hasNext() 如果向指针右侧遍历存在数字,则返回 true ;否则返回 false 。
- int next()将指针向右移动,然后返回指针处的数字。
注意,指针初始化为一个不存在于 BST 中的数字,所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 的中序遍历中至少存在一个下一个数字。
示例:
- 输入
[“BSTIterator”, “next”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”, “next”, “hasNext”]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]- 输出
[null, 3, 7, true, 9, true, 15, true, 20, false]- 解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
// 定义一个BSTIterator类,用于迭代二叉搜索树(BST)
class BSTIterator {
// 定义一个索引变量,用于追踪当前迭代到的元素位置
private int idx;
// 定义一个列表,用于存储二叉搜索树的中序遍历结果
private List<Integer> arr;
// 构造函数,接收一个二叉搜索树的根节点作为参数
public BSTIterator(TreeNode root) {
// 初始化索引为0
idx = 0;
// 初始化存储列表
arr = new ArrayList<Integer>();
// 调用中序遍历方法,将遍历结果存入列表
inorderTraversal(root, arr);
}
// 返回下一个最小的元素,并将索引加1
public int next() {
return arr.get(idx++);
}
// 判断是否还有下一个元素可供迭代
public boolean hasNext() {
return idx < arr.size();
}
// 定义一个私有方法,用于执行二叉搜索树的中序遍历
private void inorderTraversal(TreeNode root, List<Integer> arr) {
// 如果当前节点为空,则直接返回
if (root == null) {
return;
}
// 先递归遍历左子树
inorderTraversal(root.left, arr);
// 将当前节点的值添加到列表中
arr.add(root.val);
// 再递归遍历右子树
inorderTraversal(root.right, arr);
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
✨ 这就是今天要分享给大家的全部内容了,我们下期再见!😊
🏠 我在CSDN等你哦!我的主页😍