代码随想录算法刷题训练营day23：LeetCode(669)修剪二叉搜索树、LeetCode(108)将有序数组转换为二叉搜索树、LeetCode(538)把二叉树转化为累加树

LeetCode(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) {//注意是二叉搜索树，一定要按二叉搜索树的规则来做//采用先序递归的方法来做//判断终止条件-----返回为nullif(root==null){return null;}//判断树的节点是否在区间里面，若树的节点不在区间则进行删除-----根节点被删除的情况，判断左右子树的保留情况if(root.val<low){//仅会出现一种情况//那么此时这颗以root为根树的左子树一定不保留，右子树可能保留，也可能不保留，需要对右子树进行判断TreeNode right=trimBST(root.right, low, high);return right;//此时直接将右子树判断的结果返回----直接返回，后面能接住}if(root.val>high){//进入之后直接把左节点返回回去了，相当于把节点直接删除了//那么此时这颗树的右子树一定不保留，左子树可能保留，需要对左子树进行判断TreeNode left=trimBST(root.left, low, high);return left;}//递归程序开始，采用先序遍历，采用根左右的方法root.left=trimBST(root.left, low, high);//左边树处理后返回根节点root.right=trimBST(root.right, low, high);//右边树处理后返回根节点return root;}
}

LeetCode(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) {//构造平衡二叉树-------思路，主要是切割区间----注意切割区间的终止条件//定义一个新的构建二叉树的方法，用于构建新的二叉树int left=0;//定义左参数，左区间int right=nums.length-1;TreeNode root=buildTreeNode(nums,left,right);return root;}//定义构建平衡二叉树的方法public TreeNode buildTreeNode(int[] nums,int left,int right){//采用左闭右闭的方法//判断终止条件-----即为构建不了二叉树的方法if(left>right){return null;}//单次递归的执行策略int mid=(left+right)/2;TreeNode root=new TreeNode(nums[mid]);//递归----先序遍历---根左右root.left=buildTreeNode(nums, left, mid-1);//左子树root.right=buildTreeNode(nums, mid+1, right);//右子树return root;}
}

LeetCode(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 pre=0;public TreeNode convertBST(TreeNode root) {//回顾一下数组的操作方法，双指针//本题主要是更新节点的值updateTreeNodeVal(root);//将树的根节点传入进去//更新完成之后返回rootreturn root;}public void updateTreeNodeVal(TreeNode root){//终止条件if(root==null){return;}updateTreeNodeVal(root.right);//中间节点的处理逻辑//此时到了最后一个节点值root.val=root.val+pre;//此时记录的是当前节点值pre=root.val;//要理解清楚，不要绕进去//第一个更新的是最右边-根-左updateTreeNodeVal(root.left);}
}