本文主要是介绍代码随想录-算法训练营day23【二叉树09:修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客
第六章 二叉树part09今日内容:● 669. 修剪二叉搜索树
● 108.将有序数组转换为二叉搜索树
● 538.把二叉搜索树转换为累加树
● 总结篇 详细布置 669. 修剪二叉搜索树 这道题目比较难,比 添加增加和删除节点难的多,建议先看视频理解。题目链接/文章讲解: https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解: https://www.bilibili.com/video/BV17P41177ud 108.将有序数组转换为二叉搜索树 本题就简单一些,可以尝试先自己做做。https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1uR4y1X7qL 538.把二叉搜索树转换为累加树 本题也不难,在 求二叉搜索树的最小绝对差 和 众数 那两道题目 都讲过了 双指针法,思路是一样的。https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1d44y1f7wP总结篇 好了,二叉树大家就这样刷完了,做一个总结吧https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html 往日任务
● day 1 任务以及具体安排:https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排:https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排:https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排:https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排:https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排:https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排:https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排:https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排:https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排:https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排:https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排:https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排:https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排:https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排:https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排:https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排:https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH
●day 21 任务以及具体安排:https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X
●day 22 任务以及具体安排:https://docs.qq.com/doc/DUHplVUp5YnN1bnBL
目录
0669_修剪二叉搜索树
0108_将有序数组转换为二叉搜索树
0538_把二叉搜索树转换为累加树
总结篇
0669_修剪二叉搜索树
递归
- 701.二叉搜索树中的插入操作
- 450.删除二叉搜索树中的节点
- 669.修剪二叉搜索树
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;public class _0669_修剪二叉搜索树 {
}/*** 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 Solution0669 {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null) {return null;}if (root.val < low) {return trimBST(root.right, low, high);}if (root.val > high) {return trimBST(root.left, low, high);}//root在[low,high]范围内root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}//iteration,迭代法public TreeNode trimBST2(TreeNode root, int low, int high) {if (root == null)return null;while (root != null && (root.val < low || root.val > high)) {if (root.val < low)root = root.right;elseroot = root.left;}TreeNode curr = root;//deal with root's left sub-tree, and deal with the value smaller than low.while (curr != null) {while (curr.left != null && curr.left.val < low) {curr.left = curr.left.right;}curr = curr.left;}//go back to root;curr = root;//deal with root's righg sub-tree, and deal with the value bigger than high.while (curr != null) {while (curr.right != null && curr.right.val > high) {curr.right = curr.right.left;}curr = curr.right;}return root;}
}
0108_将有序数组转换为二叉搜索树
做这道题目之前大家可以了解一下这几道:
- 106.从中序与后序遍历序列构造二叉树(opens new window)
- 654.最大二叉树 (opens new window)中其实已经讲过了,如果根据数组构造一棵二叉树。
- 701.二叉搜索树中的插入操作(opens new window)
- 450.删除二叉搜索树中的节点
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.LinkedList;
import java.util.Queue;public class _0108_将有序数组转换为二叉搜索树 {
}/*** 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 Solution0108 {//递归:左闭右开,[left, right)public TreeNode sortedArrayToBST(int[] nums) {return sortedArrayToBST(nums, 0, nums.length);}public TreeNode sortedArrayToBST(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {return new TreeNode(nums[left]);}int mid = left + (right - left) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = sortedArrayToBST(nums, left, mid);root.right = sortedArrayToBST(nums, mid + 1, right);return root;}
}class Solution0108_2 {//递归:左闭右闭,[left, right]public TreeNode sortedArrayToBST(int[] nums) {TreeNode root = traversal(nums, 0, nums.length - 1);return root;}//左闭右闭区间[left, right]private TreeNode traversal(int[] nums, int left, int right) {if (left > right) return null;int mid = left + ((right - left) >> 1);TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums, left, mid - 1);root.right = traversal(nums, mid + 1, right);return root;}
}class Solution0108_3 {//迭代:左闭右闭,[left, right]public TreeNode sortedArrayToBST(int[] nums) {if (nums.length == 0) return null;//根节点初始化TreeNode root = new TreeNode(-1);Queue<TreeNode> nodeQueue = new LinkedList<>();Queue<Integer> leftQueue = new LinkedList<>();Queue<Integer> rightQueue = new LinkedList<>();// 根节点入队列nodeQueue.offer(root);// 0为左区间下标初始位置leftQueue.offer(0);// nums.size() - 1为右区间下标初始位置rightQueue.offer(nums.length - 1);while (!nodeQueue.isEmpty()) {TreeNode currNode = nodeQueue.poll();int left = leftQueue.poll();int right = rightQueue.poll();int mid = left + ((right - left) >> 1);// 将mid对应的元素给中间节点currNode.val = nums[mid];// 处理左区间if (left <= mid - 1) {currNode.left = new TreeNode(-1);nodeQueue.offer(currNode.left);leftQueue.offer(left);rightQueue.offer(mid - 1);}// 处理右区间if (right >= mid + 1) {currNode.right = new TreeNode(-1);nodeQueue.offer(currNode.right);leftQueue.offer(mid + 1);rightQueue.offer(right);}}return root;}
}
0538_把二叉搜索树转换为累加树
package com.question.solve.leetcode.programmerCarl2._07_binaryTrees;import java.util.Stack;public class _0538_把二叉搜索树转换为累加树 {
}class Solution0538 {int sum;public TreeNode convertBST(TreeNode root) {sum = 0;convertBST1(root);return root;}//按右中左顺序遍历,累加即可public void convertBST1(TreeNode root) {if (root == null) {return;}convertBST1(root.right);sum += root.val;root.val = sum;convertBST1(root.left);}
}class Solution0538_2 {//DFS iteraion统一迭代法public TreeNode convertBST(TreeNode root) {int pre = 0;Stack<TreeNode> stack = new Stack<>();if (root == null) //edge case checkreturn null;stack.add(root);while (!stack.isEmpty()) {TreeNode curr = stack.peek();//curr != null的状况,只负责存node到stack中if (curr != null) {stack.pop();if (curr.left != null) //左stack.add(curr.left);stack.add(curr); //中stack.add(null);if (curr.right != null) //右stack.add(curr.right);} else {//curr == null的状况,只负责做单层逻辑stack.pop();TreeNode temp = stack.pop();temp.val += pre;pre = temp.val;}}return root;}
}
总结篇
难,多复习,多总结。
这篇关于代码随想录-算法训练营day23【二叉树09:修剪二叉搜索树、将有序数组转换为二叉搜索树、把二叉搜索树转换为累加树】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!