235. 二叉搜索树的最近公共祖先
题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
又玩了一天,手又生疏了好多;
这道题看了题解,先用公共解法了,之前的题没刷,就给现在留坑了
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
//递归:搜索左子树,搜索右子树,若都搜索到结果即使自己(暂时不考虑自身)
//暂且不考虑二叉搜索树性质
var lowestCommonAncestor = function(root, p, q) {
if(root == null||root == p||root == q){
return root
}
let lResult = lowestCommonAncestor(root.left,p,q)
let rResult = lowestCommonAncestor(root.right,p,q)
if(lResult !=null&&rResult!=null){
return root
}else if(lResult!=null){
return lResult
}else if(rResult!=null){
return rResult
}
else{
return null
}
};
//犯错:审题出错,把,p,q当成值而非结点;
看了文章后,发现可以直接利用性质,第一个到区间中央的就是了
虽然,后面看了文章代码后发现只用遍历一条边就够了,还是不够高效
var lowestCommonAncestor = function(root, p, q) {
if(root == null){
return root
}
if(root.val>=Math.min(p.val,q.val)&&root.val<=Math.max(p.val,q.val)){
return root
}
let lResult = lowestCommonAncestor(root.left,p,q)
if(lResult!=null){
return lResult
}
let rResult = lowestCommonAncestor(root.right,p,q)
if(rResult!=null){
return rResult
}
return null
};
701.二叉搜索树中的插入操作
题目链接:https://leetcode.cn/problems/insert-into-a-binary-search-tree/
递归是很显然的,小于,插不进去就插左子树,大于同理
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
var insertIntoBST = function(root, 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
};
//错误:经典递归忘参数
450.删除二叉搜索树中的节点
题目链接:https://leetcode.cn/problems/delete-node-in-a-bst
这个看了题解
没想到可以把左子树直接接到右子树的最左边
递归返回根节点引用也很巧妙
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
//看了题解,五种情况:
//没找到
//左右孩子为空:直接删
//左/右孩子为空,用那一个取代
//左右孩子都不为空:将左孩子放在右孩子的最左面节点的左孩子上
var deleteNode = function(root, key) {
if(root == null){
return null
}
if(key == root.val){
if(root.left==null){
return root.right
}else if(root.right == null){
return root.left
}else{
let p = root.right;
while(p.left!=null){
p = p.left
}
p.left = root.left
return root.right
}
}else{
root.left = deleteNode(root.left,key)
root.right = deleteNode(root.right,key)
}
return root
};