LeetCode538.把二叉搜索树转换为累加树
public TreeNode convertBST(TreeNode root) {reverseIn(root);return root;}public Integer value=0,flag=0;public void reverseIn(TreeNode root) {if(root==null) return ;reverseIn(root.right);if(flag==0) {value=root.val;flag=1;}else {value+=root.val;root.val=value;}reverseIn(root.left);}
LeetCode108.将有序数组转换为二叉搜索树
public TreeNode sortedArrayToBST(int[] nums) {return builder(nums,0,nums.length-1);}public TreeNode builder(int[]nums,int start,int end) {if(end<start) return null;if(start==end) return new TreeNode(nums[start]);int min = (end+start)/2;TreeNode root = new TreeNode(nums[min]);root.left=builder(nums,start,min-1);root.right=builder(nums,min+1,end);return root;}
LeetCode669.修剪二叉搜索树
public TreeNode deleteNode(TreeNode root, int key) {// root为空情况if (root == null) return null;// 如果要删除的节点是根节点，并且只有一个孩子或者没有孩子if (root.val == key) {if (root.left == null) return root.right;if (root.right == null) return root.left;// 找到右子树的最左节点TreeNode minRight = root.right;while (minRight.left != null) {minRight = minRight.left;}minRight.left = root.left;return root.right;}// 保存根节点TreeNode head = root;TreeNode temp = root;// 找到要删除的节点while (root != null && root.val != key) {temp = root;if (root.val > key) {root = root.left;} else {root = root.right;}}// 不存在 key 节点if (root == null) return head;// 删除节点if (root.left == null && root.right == null) {if (temp.left == root) {temp.left = null;} else {temp.right = null;}} else if (root.left == null) {if (temp.left == root) {temp.left = root.right;} else {temp.right = root.right;}} else if (root.right == null) {if (temp.left == root) {temp.left = root.left;} else {temp.right = root.left;}} else {TreeNode minRight = root.right;while (minRight.left != null) {minRight = minRight.left;}minRight.left = root.left;if (temp.left == root) {temp.left = root.right;} else {temp.right = root.right;}}return head;}public TreeNode trimBST(TreeNode root, int low, int high) {head=root;in(root,low,high);return head;}public TreeNode head = null;public void in(TreeNode root,int low,int high) {if(root==null) return;in(root.left,low,high);if(root.val<low||root.val>high) {head = deleteNode(head, root.val);}in(root.right,low,high);}
