235. 二叉搜索树的最近公共祖先
思路：要利用二叉搜索数的性质。当前遍历节点 cur 的数值大于p q时，说明 p q 的父节点在 cur 的左子树。当前遍历节点 cur 的数值小于p q时，说明 p q 的父节点在 cur 的右子树。当前遍历节点 cur 的数值在 p q 之间时，说明 cur 是 p q 的父节点。
cur是公共祖先，他一定是最近的公共祖先吗？是的，一定是。
根本不需要遍历到pq因为二叉搜索树有特性。
- 出错
错误
Line 23: error: missing return statement}^
这两种写法都是不对的，因为出了if else没有返回值
- 正确写法
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(p.val<root.val && q.val<root.val) {return lowestCommonAncestor(root.left, p,q);} else if(p.val>root.val && q.val>root.val) {return lowestCommonAncestor(root.right, p,q);}return root;}
}
701.二叉搜索树中的插入操作
- 写错了
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null) {TreeNode tmp = new TreeNode(); // TreeNode<Integer>tmp = new TreeNode<>();这里不能这么写tmp.val = val;root = tmp;return root;}if(val > root.val){return insertIntoBST(root.right, val);}if(val < root.val){return insertIntoBST(root.left, val);}}
}
思路：插入一个节点，一定能放在叶子节点上
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null) {TreeNode tmp = new TreeNode(); // TreeNode<Integer>tmp = new TreeNode<>();这里不能这么写tmp.val = val;return tmp;}if(val > root.val){//插入到他的右节点root.right = insertIntoBST(root.right, val);}if(val < root.val){root.left = insertIntoBST(root.left, val);}return root;}
}
450.删除二叉搜索树中的节点
1没找到删除的节点
2找到了待删除的节点cur
①cur是叶子节点，直接删除
②cur左子树不为空，右子树为空 => cur 父节点直接指向 cur的 左孩子节点
③cur左空右不空 => cur 父节点直接指向 cur的 右孩子节点
④cur左右都不空，选right右孩子继位（左也行），那么他的左子树放在哪里？放在right左子树最下面的一个
错误示范
一个函数找目标节点，另一个函数删除可行吗？不可行，因为要返回处理后的树给父节点，要用到递归。
class Solution {TreeNode target;public TreeNode deleteNode(TreeNode root, int key) {//找目标删除节点findNode(root, key);if(target == null) return null;deleteDetail(target);}public void findNode(TreeNode root, int key) {if(key > root.val) {findNode(root.right);}if(key < root.val) {findNode(root.left);}if(key == root.val) {target = root;}}public void deleteDetail(TreeNode cur) {//叶子节点}
}
正确答案
class Solution {public TreeNode deleteNode(TreeNode root, int key) {return deleteDetail(root,key);}//怎么表示找不到值为key的节点?//这个问题纯纯是题目没看明白，如果二叉树不为空，但找不到为KEY的节点，返回原二叉树public TreeNode deleteDetail(TreeNode cur,int key) {if(cur == null) {return null;}if(key > cur.val) {cur.right = deleteDetail(cur.right, key); //在cur的右子树处理完，返回给右节点}else if(key < cur.val) {cur.left = deleteDetail(cur.left, key);}if(key == cur.val) {//叶子节点if(cur.left == null && cur.right == null) {return null;}//只有左子树else if(cur.right == null) {return cur.left;}//只有右子树else if(cur.left == null) {return cur.right;}//左右孩子都有else {TreeNode node = cur.right;while(node.left!=null) node=node.left;node.left = cur.left;return cur.right;}}return cur;}
}
优化
优化：这种方法会让树的高度变很大，可以找右数最小去替代待删除的节点，只用交换右数最小和删除结点的值，然后就变成了删除右树最小的节点，这个节点一定是个叶子节点，树的结构变化小。
上面说法是B站代码随想录弹幕说的，但经我实践是错误的，因为右树(cur=root.right)最小的节点不一定是个叶子节点，可能没有左子树，那么根节点 cur 就是最小的。交换不了
这个应该可以，但好麻烦啊。
