235.二叉搜索树的最近公共祖先
题目链接：力扣
思路
这道题目比236.二叉树的最近公共祖先更有特殊性，所以使用一般二叉树的最近公共祖先的查找方法完全是可以的
然后就是利用二叉树的特性进行判断了
二叉搜索树的最近公共祖先
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root.val > p.val && root.val > q.val) { TreeNode left = lowestCommonAncestor(root.left,p,q); if (left != null) { return left; } } else if (root.val < p.val && root.val < q.val) { TreeNode right = lowestCommonAncestor(root.right,p,q); if (right != null) { return right; } } else { return root; } return null; } }
一般方法
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root == q || root == p) { return root; } // 左 TreeNode left = lowestCommonAncestor(root.left,p,q); // 右 TreeNode right = lowestCommonAncestor(root.right,p,q); // 中 if (left != null && right != null) { return root; } else if (left == null && right != null){ return right; } else if (left != null && right == null) { return left; } return null; } }
针对搜索树
二叉搜索树是有顺序的，使用二叉搜索树的有序性可以确定搜索的方向
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return null; } if (root.val > p.val && root.val > q.val) { TreeNode left = lowestCommonAncestor(root.left,p,q); if (left != null) { return left; } } else if (root.val < p.val && root.val < q.val) { TreeNode right = lowestCommonAncestor(root.right,p,q); if (right != null) { return right; } } else { return root; } return null; } }
迭代法
要合理运用数据结构的特性，不要拘泥于方法
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (true) { if (root.val > p.val && root.val > q.val) { root = root.left; } else if (root.val < p.val && root.val < q.val) { root = root.right; } else { break; } } return root; } }
701.二叉搜索树中的插入操作
题目链接：力扣
思路
找到位置，赋值
二叉搜索树中的插入操作
迭代法
很直接 找到位置 赋值
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } TreeNode cur = root; while (true) { if (val < cur.val ) { if (cur.left != null) { cur = cur.left; } else { cur.left = new TreeNode(val); break; } } else if (val > cur.val) { if (cur.right != null) { cur = cur.right; } else { cur.right = new TreeNode(val); break; } } } return root; } }
递归法
class Solution { public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (root.val < val) { root.right = insertIntoBST(root.right,val); } else if (root.val > val) { root.left = insertIntoBST(root.left, val); } return root; } }
450.删除二叉搜索树中的节点
题目链接：力扣
思路
情况1：没找到要删除的节点
情况2：找到了删除的节点
删除的节点是叶子节点（节点左为空，右为空）
直接删除叶子节点
删除的节点有一棵子树（节点左不空右为空，或者节点左为空右不空）
让父节点跨过指向子树就可以
删除的节点有两个子树（节点左不空，右也不空）
最为复杂的一种情况
首先让左子树或者右子树继位
假设让右子树继位，左子树一堆的数字应该继位到右子树的后面
右子树都是比删除节点大的，所以在右子树中应该找一个比删除节点大最小的树，那就是左子树的最左侧的节点
将左子树整体添加到这个节点上
删除二叉搜索树中的节点
因为找到节点后，就要进行删除，所以删除的代码逻辑就在终止条件中
class Solution { public TreeNode deleteNode(TreeNode root, int key) { // 终止条件 和 删除各种情况的节点 if (root == null) { // 情况1：没找到要删除的节点 return null; } 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.right != null && root.left == null) { // 删除的节点有一棵子树（节点左为空右不空） return root.right; } else { // 删除的节点有两个子树（节点左不空，右也不空） TreeNode cur = root.right; // 记录是删除节点的右子树，一会让右子树继位，指针指向，是为了给删除节点的左子树找位置(右子树中的最小值，右子树最左边的节点) while (cur.left != null) { // 找到右子树中的最小值 cur = cur.left; } cur.left = root.left; // 给左子树找好位置 return root.right; // 右子树继位 } } if (key > root.val) { root.right = deleteNode(root.right,key); } if (key < root.val) { root.left = deleteNode(root.left,key); } return root; } }
