构建二叉树搜索树算法题总结(第三十天)

本文主要是介绍构建二叉树搜索树算法题总结(第三十天)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

701. 二叉搜索树中的插入操作

题目

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

答案

class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root==null){return new TreeNode(val);}if(val<root.val){root.left = insertIntoBST(root.left,val);}if(val>root.val){root.right = insertIntoBST(root.right,val);}return root;}
}

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

题目

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

答案

class Solution {public TreeNode deleteNode(TreeNode root, int key) {if(root==null){return root;}//根 左 右if(root.val==key){if(root.left==null && root.right==null){return null;}else if(root.left!=null && root.right==null){return root.left;}else if(root.left==null && root.right!=null){return root.right;}else{TreeNode right = root.right;while(right.left!=null){right = right.left;}right.left = root.left;return root.right;}}root.left = deleteNode(root.left,key);root.right = deleteNode(root.right,key);return root;}
}

669. 修剪二叉搜索树

题目

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

答案

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;}
}

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

题目

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

答案

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

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

题目

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

答案

class Solution {int res = 0;public TreeNode convertBST(TreeNode root) {if(root==null){return root;}//右 根 左convertBST(root.right);res += root.val;root.val = res;convertBST(root.left);return root;}
}