力扣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/
思路:在二叉搜索樹中搜索值,只需要利用二叉搜索樹的特性,val<root.val 去左子樹進行搜索,val>root.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
②、返回另一個非空的孩子節點。
③、有兩種刪除方法,可以拿當前節點的左子樹中最大值(即一路p=p.right)進行交換,然后遞歸刪除,也可以拿當前節點的右子樹中的最小值(即一路p=p.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;}
}