235.二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
和之前二叉树的最近公共祖先相同,只不过二叉搜索树更有规律。
1.当当前节点大于p、q两个节点的值,向左寻找
2.当当前节点小于p、q两个节点的值,向右寻找
3.如果值在他们中间,就说明找到了
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;}}if (root.val < p.val && root.val < q.val) {TreeNode right = lowestCommonAncestor(root.right, p, q);if (right != null) {return right;}}return root;}
}
701.二叉树搜索中的插入操作
秒了
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) {root = new TreeNode(val);return root;}insert(root, val);return root;}public void insert(TreeNode root, int val) {if (root.left == null && root.val > val) {root.left = new TreeNode(val);}if (root.right == null && root.val < val) {root.right = new TreeNode(val);}if (root.val > val) {insert(root.left, val);}if (root.val < val) {insert(root.right, val);}}
}
450.删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
还是递归,首先需要找到节点,找到节点后,根据左右孩子的情况讨论。而且需要保留它的父节点(也就是root.left=deleteNode()的意义)。
最复杂的是左右孩子都有的节点,这种情况下需要找到该节点右子树的最左边节点(左子树的值肯定比右子树的小),然后把左子树插到最左边。
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;}// 左孩子为空,右孩子不为空if (root.left == null && root.right != null) {return root.right;}// 右孩子为空,左孩子不为空if (root.right == null && root.left != null) {return root.left;}// 左右孩子都不为空// 找到右孩子的最左节点TreeNode curr = root.right;while (curr.left != null) {curr = curr.left;}// 右子树的最左节点左节点变成左孩子curr.left = root.left;return root.right;}if (root.val > key) {root.left = deleteNode(root.left, key);}if (root.val < key) {root.right = deleteNode(root.right, key);}return root;}
}