148.排序链表
给你链表的头结点 head
,请将其按升序排列并返回排序后的链表。
输入:head = [4,2,1,3]
输出:[1,2,3,4]
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
输入:head = []
输出:[]
对链表自顶向下归并排序的过程如下:
- 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 222 步,慢指针每次移动 111 步,当快指针到达链表末尾时,慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法,将两个有序的子链表进行合并。
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1,即当链表为空或者链表只包含 1个节点时,不需要对链表进行拆分和排序。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
// 主函数,调用递归排序函数
public ListNode sortList(ListNode head) {
return sortList(head, null);
}
// 递归排序函数,传入头节点和尾节点
public ListNode sortList(ListNode head, ListNode tail) {
if (head == null) {
// 如果头节点为空,直接返回
return head;
}
if (head.next == tail) {
// 如果只有一个节点,直接返回
head.next = null;
return head;
}
// 快慢指针找到中间节点
ListNode slow = head, fast = head;
while (fast != tail) {
slow = slow.next;
fast = fast.next;
if (fast != tail) {
fast = fast.next;
}
}
// 分割链表
ListNode mid = slow;
ListNode list1 = sortList(head, mid); // 对前半部分进行排序
ListNode list2 = sortList(mid, tail); // 对后半部分进行排序
// 合并两个有序链表
ListNode sorted = merge(list1, list2);
return sorted;
}
// 合并两个有序链表的函数
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0); // 创建一个哑节点作为新链表的头节点
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
// 遍历两个链表,比较节点值,将较小的节点添加到新链表中
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
// 如果第一个链表还有剩余节点,将其添加到新链表的末尾
temp.next = temp1;
} else if (temp2 != null) {
// 如果第二个链表还有剩余节点,将其添加到新链表的末尾
temp.next = temp2;
}
return dummyHead.next; // 返回新链表的头节点(去掉哑节点)
}
}
114.二叉树展开为链表
给你二叉树的根结点 root ,请你将它展开为一个单链表:
- 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
- 展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]
/** * 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 {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>(); // 创建一个列表用于存储二叉树的节点
preorderTraversal(root,list); // 对二叉树进行前序遍历,并将节点添加到列表中
for(int i=1;i<list.size();i++){
// 遍历列表中的节点
TreeNode prev = list.get(i-1),curr = list.get(i); // 获取当前节点和前一个节点
prev.left = null; // 将前一个节点的左子节点置为空
prev.right = curr; // 将前一个节点的右子节点指向当前节点
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
// 前序遍历二叉树的方法
if (root != null) {
// 如果当前节点不为空
list.add(root); // 将当前节点添加到列表中
preorderTraversal(root.left, list); // 递归遍历左子树
preorderTraversal(root.right, list); // 递归遍历右子树
}
}
}
637.二叉树的层平均值
给定一个非空二叉树的根节点 root
, 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
输入:root = [3,9,20,null,null,15,7]
输出:[3.00000,14.50000,11.00000]
解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
/** * 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 {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>(); // 创建一个列表用于存储每一层节点的平均值
bfs(root, result); // 调用广度优先搜索方法
return result; // 返回结果列表
}
public void bfs(TreeNode root, List<Double> result) {
if (root == null) {
// 如果根节点为空,直接返回
return;
}
Queue<TreeNode> queue = new LinkedList<>(); // 创建一个队列用于存储节点
queue.offer(root); // 将根节点加入队列
while (!queue.isEmpty()) {
// 当队列不为空时,继续循环
double sum = 0; // 初始化当前层节点值之和为0
int size = queue.size(); // 获取当前层的节点数量
for (int i = 0; i < size; i++) {
// 遍历当前层的节点
TreeNode node = queue.poll(); // 取出队首节点
sum += node.val; // 累加节点值
if (node.left != null) {
// 如果左子节点不为空,将其加入队列
queue.offer(node.left);
}
if (node.right != null) {
// 如果右子节点不为空,将其加入队列
queue.offer(node.right);
}
}
result.add(sum / size); // 计算当前层节点值的平均值,并加入结果列表
}
}
}
112.路径总和
给你二叉树的根节点 root
和一个表示目标和的整数 targetSum
。判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和 targetSum
。如果存在,返回 true
;否则,返回 false
。叶子节点是指没有子节点的节点。
输入:root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出:true
解释:等于目标和的根节点到叶节点路径如上图所示。
输入:root = [1,2,3], targetSum = 5
输出:false
解释:树中存在两条根节点到叶子节点的路径:
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
/** * 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 {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return false;
}
// 如果当前节点是叶子节点(即左右子节点都为空),检查路径和是否等于目标值
if(root.left == null && root.right == null){
return root.val == targetSum;
}
// 如果当前节点不是叶子节点,递归地在左子树和右子树中查找路径
// 路径和等于目标值减去当前节点的值
return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}
}
222.完全二叉树的节点个数
给你一棵完全二叉树的根节点 root
,求出该树的节点个数。
完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h
层,则该层包含 1~ 2h
个节点。
输入:root = [1,2,3,4,5,6]
输出:6
输入:root = []
输出:0
输入:root = [1]
输出:1
/** * 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 {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int left = countNodes(root.left);
int right = countNodes(root.right);
return left+right+1;
}
}
文章评论