本文主要是介绍Rubyr代码随想录算法训练营第22天|● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode 235. 二叉搜索树的最近公共祖先
1) base case: 如果root == null, 直接返回null;
2) 如果root的val等于两点中的其中一个节点，则返回root;
3）没有的话遍历左右子树，如果左右子树的结果最后都不返回null，说明在左右子树找到了两节点，并返回当前根节点；
4） 如果左右子树的结果没有都返回nul，看哪一个子树结果不是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) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left != null && right != null) {return root;}return (left != null) ? left : right;}
}leetcode 701.二叉搜索树中的插入操作
用分解遍历的方式，这样能给插入的节点放到左子树或右子树
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {return new TreeNode(val);}if (root.val > val) {root.left = insertIntoBST(root.left, val);}if (root.val < val) {root.right = insertIntoBST(root.right, val);}return root;}}Leetcode450. 删除二叉搜索树中的节点
1) 注意BST 的每个节点应该要小于右边子树的所有节点;
2)root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val;
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;}if (root.right == null) {return root.left;}//if left and right are not equal to null; get the min node from right subtreeTreeNode minNode = root.right;while (minNode.left != null) {minNode = minNode.left;}root.val = minNode.val;//删除minNode 所在的节点root.right = deleteNode(root.right, minNode.val);}return root;}
}这篇关于Rubyr代码随想录算法训练营第22天|● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
