力扣爆刷第144天之二叉树四连刷（完结二叉搜索树改变树结构）

本文主要是介绍力扣爆刷第144天之二叉树四连刷（完结二叉搜索树改变树结构），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣爆刷第144天之二叉树五连刷（二叉搜索树）

一、450. 删除二叉搜索树中的节点

题目链接：https://leetcode.cn/problems/delete-node-in-a-bst/description/
思路：删除二叉搜索树中的节点，这种改变树结构类型的题目，一定都是在树的遍历过程中，构造树，这个是一个解题的模板，也就是递归函数的返回值要作为父节点的左孩子或者右孩子。本题直接从上往下搜索，一旦搜索到，有两种解题方案，一种是找到左子树的最大值或者右子树的最小值，找到后替换子树的链接，然后作为root返回。注意边界条件控制。

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;if(root.val > key) {root.left = deleteNode(root.left, key);}else if(root.val < key) {root.right = deleteNode(root.right, key);}else{if(root.left == null) return root.right;TreeNode p = root.left;TreeNode pro = p;while(p.right != null) {pro = p;p = p.right;}if(pro != p) {pro.right = p.left;p.left = root.left;p.right = root.right;}else{p.right = root.right;}return p;}return root;}
}

二、669. 修剪二叉搜索树

题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/description/
思路：和上一题类似，不过简单那很多，只需要递归遍历搜索到边界条件处即可停止。在遍历的过程中构建树，如果当前节点不在范围内，则直接返回子树结果（就是在结果树中剔除了当前节点），如果当前结果在范围内，则构建树，即用root的左右孩子接收递归寻找结果。

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root == null) return null;if(root.val > high) {return trimBST(root.left, low, high);}else if(root.val < low) {return trimBST(root.right, low, high);}else {root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}}
}

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

题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
思路：通过有序数组构建平衡二叉搜索树，只需要采用二分查找的方法来构建二叉树，构建处来的一定是平衡二叉搜素树。

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

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

题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/description/
思路：让把二叉搜索树改成累加树，累加树的要求是新节点为原节点加上比它大的所有节点，所以利用中序遍历的特性，采用右，中，左的方式进行遍历累加即可。

class Solution {int sum = 0;public TreeNode convertBST(TreeNode root) {traverse(root);return root;}void traverse(TreeNode root) {if(root == null) return;traverse(root.right);root.val += sum;sum = root.val;traverse(root.left);}
}

这篇关于力扣爆刷第144天之二叉树四连刷（完结二叉搜索树改变树结构）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---