LeetCode 235. 二叉搜索树的最近公共祖先
分析1.0
二叉搜索树根节点元素值大小介于子树之间，所以只要找到第一个介于他俩之间的节点就行
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val >= p.val && root.val <= q.val){
return root;
}else if(root.val >= q.val && root.val <= p.val){
return root;
}
else if(root.val >= p.val && root.val >= q.val){
return lowestCommonAncestor(root.left, p, q);
}else{
return lowestCommonAncestor(root.right, p, q);
}
}
}LeetCode 701.二叉搜索树中的插入操作
分析1.0
搜索树插入的新节点替代了原本的空分叉
find 空分叉 插入
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
if(val > root.val){
if(root.right == null){
root.right = new TreeNode(val);
}else {
insertIntoBST(root.right, val);
}
}else{
if(root.left == null){
root.left = new TreeNode(val);
}else {
insertIntoBST(root.left, val);
}
}
return root;
}
}ps. 这里先确定是左边，再看是否为空的思路挺好
LeetCode 450.删除二叉搜索树中的节点
分析1.0
删除节点，找到节点分情况讨论
- 节点是叶子节点，直接删除
节点是分支节点，找左子树的最大值或右子树的最小值节点的pre节点，左树最大值节点可能有左子树，右树最小值节点可能有右子树，pre节点还可能是当前节点
- 有左子树有右子树
有左子树无右子树
无左子树有右子树
删除节点要知道这个节点的父节点 每次递归前先令pre = 当前节点
还要清楚待删节点是父节点的左节点还是右节点，设置参数flag指示
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null){
return null;
}
TreeNode pre = new TreeNode(-1);
pre.left = root;
pre.right = root;
return delete(root, key, pre, 0);
}
public TreeNode delete(TreeNode root, int key, TreeNode pre, int flag){
if(root == null){
return null;
}
if(key > root.val){
flag = 1;
pre = root;
delete(root.right, key, pre, flag);
}else if(key < root.val){
flag = -1;
pre = root;
delete(root.left, key, pre, flag);
}else {
// 是叶节点
if(root.left == null && root.right == null){
if(pre.val == -1){
return null;
}
if(flag == -1){
pre.left = null;
}else{
pre.right = null;
}
}
// 分支节点 有左子树没右子树 有左子树有右子树 找左子树最大节点的父节点
else if(root.left != null){
TreeNode target = findLeftTree(root.left, root);
// 如果target是左子树树根-左子树无右子树
int swap = 0;
if(target.val == root.val){
swap = target.left.val;
target.left = root.left.left;
}else{
swap = target.right.val;
// 可能最大节点target.right有左子树
target.right = target.right.left;
}
//System.out.println("pre节点为"+pre.val);
if(flag == -1){
pre.left.val = swap;
}else{
pre.right.val = swap;
}
}
// 分支节点 有右子树没左子树
else if(root.right != null && root.left == null){
TreeNode target = findRightTree(root.right, root);
int swap = 0;
if(target.val == root.val){
swap = target.right.val;
target.right = target.right.right;
}else{
swap = target.left.val;
target.left = target.left.right;
}
//System.out.println("target节点为"+pre.val);
if(flag == -1){
pre.left.val = swap;
}else{
pre.right.val = swap;
}
}
// 分支节点
}
return root;
}
// pre为待删除分支节点 左子树不为空 右子树空 找左子树最大节点
public TreeNode findLeftTree(TreeNode root, TreeNode pre){
//System.out.print("以"+root.val+"为根节点的树的最大节点为");
while(root.right != null){
pre = root;
root = root.right;
}
//System.out.println(root.val+"target节点为"+pre.val);
return pre;
}
// pre为待删除分支节点 右子树不为空 找右子树最小节点
public TreeNode findRightTree(TreeNode root, TreeNode pre){
//System.out.print("以"+root.val+"为根节点的树的最大节点为------");
while(root.left != null){
pre = root;
root = root.left;
}
//System.out.println(root.val+"它的pre节点为"+pre.val);
return pre;
}
}lieetcode 上看到一个思路
如果目标节点大于当前节点值，则去右子树中删除；
如果目标节点小于当前节点值，则去左子树中删除；
如果目标节点就是当前节点，分为以下三种情况：
其无左子：其右子顶替其位置，删除了该节点；
其无右子：其左子顶替其位置，删除了该节点；
其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
总结
- 头脑中要有一棵树，树形象上的特点，遍历序列上的特点
一定要先想清楚代码逻辑、循环逻辑、递归逻辑再继续
我的做题思维通常都是用代码模拟人脑
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
