算法训练营day23(二叉树09:修建二叉搜索树,有序数组转化为平衡二叉搜索树,二叉搜索树转化为累加树,二叉树专题总结)

2024/12/4 5:00:04 来源：https://blog.csdn.net/weixin_61931006/article/details/144180311 浏览: 次关键词：算法训练营day23(二叉树09:修建二叉搜索树,有序数组转化为平衡二叉搜索树,二叉搜索树转化为累加树,二叉树专题总结)

第六章 二叉树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

day23

修建二叉树

递归法

 class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if( root == null) return root;if( root.val > high ) {//return right ;return trimBST( root.left, low, high);//修建右子树,返回right给上一层}else if( root.val < low){return trimBST(root.right, low, high);}//root在left和right之间root.left = trimBST( root.left,low,high);root.right = trimBST( root.right,low,high);return root;}}

数组构造平衡二叉搜索树

迭代法

 class Solution {public TreeNode sortedArrayToBST(int[] nums) {return traversal( nums, 0, nums.length - 1);}public TreeNode traversal( int[] nums, int left,int right) {if( left > right) return null;int mid = (left + right) >>> 1;TreeNode root = new TreeNode(nums[mid]);root.left = traversal(nums, left, mid - 1);root.right = traversal(nums, mid + 1, right);return root;}}

二叉树转换为累加树

递归法

 class Solution {int pre = 0;public TreeNode convertBST(TreeNode root) {//左中右从小到大,右中左从大到小if( root ==null) return null;convertBST (root.right);root.val += pre;pre = root.val;convertBST( root.left); return root;}}//其实拆开成traversal和converBST也行