网站建设的电销,遵义网约车平台,手机快速建站,备案个人网站名称推荐力扣labuladong一刷day35天 文章目录 力扣labuladong一刷day35天一、98. 验证二叉搜索树二、700. 二叉搜索树中的搜索三、701. 二叉搜索树中的插入操作四、450. 删除二叉搜索树中的节点 一、98. 验证二叉搜索树
题目链接#xff1a;https://leetcode.cn/problems/validate-bi…力扣labuladong一刷day35天 文章目录 力扣labuladong一刷day35天一、98. 验证二叉搜索树二、700. 二叉搜索树中的搜索三、701. 二叉搜索树中的插入操作四、450. 删除二叉搜索树中的节点 一、98. 验证二叉搜索树
题目链接https://leetcode.cn/problems/validate-binary-search-tree/ 思路校验二叉搜索树的合法性简单的想法直接遍历判断左右孩子与父节点值的关系即可但是有时候会出现问题如何 10 - { 5, 15- {6, 20} }。看似都满足其实不是的6归属于10的右子树但是却比10小这也就是说每一个root只管的了他的左右孩子但没法把约束root的信息传递给左右孩子所以我们在遍历的时候就要携带上root的约束范围向下传递。也就是说从上往下遍历的过程中记录好每一个节点的约束范围。
class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, null, null);}boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {if (root null) return true;if (min ! null root.val min.val) return false;if (max ! null root.val max.val) return false;return isValidBST(root.left, min, root) isValidBST(root.right, root, max);}
}二、700. 二叉搜索树中的搜索
题目链接https://leetcode.cn/problems/search-in-a-binary-search-tree/ 思路在二叉搜索树中搜索值只需要利用二叉搜索树的特性valroot.val 去左子树进行搜索valroot.val去右子树搜索 val root.val 返回。
class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root null) return null;if (val root.val) return searchBST(root.left, val);if (val root.val) return searchBST(root.right, val);return root;}
}三、701. 二叉搜索树中的插入操作
题目链接https://leetcode.cn/problems/insert-into-a-binary-search-tree/ 思路对于二叉搜索树的插入和查询思路是类似的左右判断一路向下搜索为node null就找到了位置new 新节点返回就是。
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. 删除二叉搜索树中的节点
题目链接https://leetcode.cn/problems/delete-node-in-a-bst/ 思路其实对于二叉搜索树的查找、新增、修改都是一样的思路对于删除却不一样有3中可能性①、要删除节点为叶子节点。②、要删除节点只有一个孩子节点。③、要删除节点有两个孩子节点。 ①、直接返回null ②、返回另一个非空的孩子节点。 ③、有两种删除方法可以拿当前节点的左子树中最大值即一路pp.right进行交换然后递归删除也可以拿当前节点的右子树中的最小值即一路pp.left进行交换然后递归删除。
class Solution {public TreeNode deleteNode(TreeNode root, int key) {if (root null) return null;if (key root.val) {if (root.left null root.right null) return null;if (root.left null root.right ! null) return root.right;if (root.left ! null root.right null) return root.left;TreeNode p root.right;while (p.left ! null) {p p.left;}root.val p.val;root.right deleteNode(root.right, root.val);} else if (key root.val) {root.left deleteNode(root.left, key);}else {root.right deleteNode(root.right, key);}return root;}
}
