二叉树习题其五【力扣】【算法学习day.12】
前言
书接上篇文章二叉树习题其四,这篇文章我们将基础拓展
###我做这类文档一个重要的目的还是给正在学习的大家提供方向(例如想要掌握基础用法,该刷哪些题?)我的解析也不会做的非常详细,只会提供思路和一些关键点,力扣上的大佬们的题解质量是非常非常高滴!!!
习题
1.二叉树的最近公共祖先
题目链接:236. 二叉树的最近公共祖先 - 力扣(LeetCode)
题面:
基本分析:如果一个节点的左右子树含有目标值,那么这个节点就是祖先,如果只有左/右子树含有,那这个就不是祖先
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode res;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
recursion(root,p.val,q.val);
return res;
}
public int recursion(TreeNode node,int a,int b){
if(node==null)return 0;
int c = node.val==a|node.val==b?1:0;
int left = recursion(node.left,a,b);
int right = recursion(node.right,a,b);
if(c+left+right==2)res = node;
return c+left+right==0?0:1;
}
}
2.二叉搜索树中的插入操作
题目链接:701. 二叉搜索树中的插入操作 - 力扣(LeetCode)
题面:
基本分析:根据二叉搜索树的规则一直遍历到空值然后插入即可
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int res;
TreeNode flag;
public TreeNode insertIntoBST(TreeNode root, int val) {
// System.out.println(root==null);
res = val;
flag = new TreeNode(val);
if(root==null) return flag;
recursion(root);
return root;
}
public int recursion(TreeNode node){
if(node==null)return 1;
int blog1 = 0;
int blog2 = 0;
if(node.val<res)blog1 = recursion(node.right);
if(node.val>res)blog2 = recursion(node.left);
if(blog1==1)node.right = flag;
else if(blog2==1)node.left = flag;
return 0;
}
}
3.删除二叉搜索树中的节点
题目链接:450. 删除二叉搜索树中的节点 - 力扣(LeetCode)
题面:
基本分析:如果遍历到要删除的节点,分情况的讨论,如果左右节点都是空,就返回null,如果左/右有一个为空,就返回右/左,如果左右都不为空,则需要将子树拼接,具体看代码
代码:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int target;
public TreeNode deleteNode(TreeNode root, int key) {
target = key;
if(root==null)return null;
return recursion(root);
}
public TreeNode recursion(TreeNode node){
if(node==null)return null;
if(node.val==target){
if(node.left==null)return node.right;
if(node.right==null)return node.left;
TreeNode c = node.left;
while(c.right!=null)c = c.right;
c.right = node.right;
return node.left;
}else{
if(node.val>target)node.left = recursion(node.left);
else node.right = recursion(node.right);
}
return node;
}
}
后言
上面是二叉树的部分习题,下一篇会讲解二叉树的其他相关力扣习题,希望有所帮助,一同进步,共勉!