代码随想录算法训练营第二十一天 | 669-修剪二叉搜索树、108-将有序数组转换为二叉搜索树、538-把二叉搜索树转换为累加树
LeetCode669 修剪二叉搜索树
题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/description/
文章讲解：https://programmercarl.com/0669.修剪二叉搜索树.html
视频讲解：https://www.bilibili.com/video/BV17P41177ud/?share_source=copy_web&vd_source=b989f2b109eb3b17e8178154a7de7a51
遇到需要修剪的节点，不能直接返回它的子树，还需要再对它的子树进行遍历，确保修剪彻底
class Solution {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.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
}
LeetCode108 将有序数组转换为二叉搜索树
题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
文章讲解：https://programmercarl.com/0108.将有序数组转换为二叉搜索树.html
视频讲解：https://www.bilibili.com/video/BV1uR4y1X7qL/?share_source=copy_web&vd_source=b989f2b109eb3b17e8178154a7de7a51
寻找分割点，分割点作为当前节点，然后递归左区间和右区间
坚持区间左闭右闭
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums, 0, nums.length - 1);}public TreeNode build(int[] nums, int left, int right){if(left > right){return null;}int mid = (left + right)/2;TreeNode curNode = new TreeNode(nums[mid]);curNode.left = build(nums, left, mid - 1);curNode.right = build(nums, mid + 1, right);return curNode;}
}
LeetCode538 把二叉搜索树转换为累加树
题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
文章讲解：https://programmercarl.com/0538.把二叉搜索树转换为累加树.html
视频讲解：https://www.bilibili.com/video/BV1d44y1f7wP/?share_source=copy_web&vd_source=b989f2b109eb3b17e8178154a7de7a51
定义一个全局变量pre，用来保存cur节点的前一个节点的数值
遇到空节点就返回，以右中左的顺序来遍历二叉树， 中节点的处理逻辑就是让curNode的数值加上前一个节点preNode的数值
class Solution {int preNode = 0;public TreeNode convertBST(TreeNode root) {traverse(root);return root;}public void traverse(TreeNode node){if(node == null){return;}traverse(node.right);node.val += preNode;preNode = node.val;traverse(node.left);}
}