【算法刷题day23】Leetcode:669. 修剪二叉搜索树、108. 将有序数组转换为二叉搜索树、538. 把二叉搜索树转换为累加树

草稿图网站
java的Deque

Leetcode 669. 修剪二叉搜索树

题目：669. 修剪二叉搜索树
解析：代码随想录解析

解题思路

对于不符合的节点，如果该节点小于区间，则右孩子可能符合；如果该节点大于区间，则左孩子可能符合。

代码

/*** 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 TreeNode trimBST(TreeNode root, int low, int high) {if (root == null)return root;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;}
}//迭代法
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if (root == null)return root;while (root != null && (root.val < low || root.val > high)) {if (root.val < low)root = root.right;elseroot = root.left;}TreeNode cur = root;while (cur != null) {while (cur.left != null && cur.left.val < low)cur.left = cur.left.right;cur = cur.left;}cur = root;while (cur != null) {while (cur.right != null && cur.right.val > high)cur.right = cur.right.left;cur = cur.right;}return root;}
}

总结

暂无

Leetcode 108. 将有序数组转换为二叉搜索树

题目：108. 将有序数组转换为二叉搜索树
解析：代码随想录解析

解题思路

递归+数组

代码

/*** 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 TreeNode sortedArrayToBST(int[] nums) {if (nums == null || nums.length == 0)return null;return buildTree(nums, 0, nums.length);}private TreeNode buildTree(int[] nums, int left, int right) {if (left == right)return null;if (left + 1 == right)return new TreeNode(nums[left]);int mid = left + (right - left) / 2;TreeNode midNode = new TreeNode(nums[mid]);midNode.left = buildTree(nums, left, mid);midNode.right = buildTree(nums, mid + 1, right);return midNode;}
}

总结

迭代懒得写了

Leetcode 538. 把二叉搜索树转换为累加树

题目：538. 把二叉搜索树转换为累加树
解析：代码随想录解析

解题思路

反过来的中序

代码

/*** 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 {int sum = 0;public TreeNode convertBST(TreeNode root) {if (root == null)return null;order(root);return root;}private void order(TreeNode node) {if (node == null)return;order(node.right);sum += node.val;node.val = sum;order(node.left);}
}

总结

递归懒得写