今天在力扣和牛客网上找了一下题,下面附上题目链接,大家先做题再看答案
1. 检查两颗树是否相同。100. 相同的树 - 力扣(LeetCode)
2. 另一颗树的子树。572. 另一棵树的子树 - 力扣(LeetCode)
3. 翻转二叉树。226. 翻转二叉树 - 力扣(LeetCode)
4. 判断一颗二叉树是否是平衡二叉树。110. 平衡二叉树 - 力扣(LeetCode)
5. 对称二叉树。101. 对称二叉树 - 力扣(LeetCode)
6. 二叉树的构建及遍历。二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
1,检查两棵树是否相同
题目描述:
给你两棵二叉树的根节点
p
和q
,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
思路 :递归的时候让两棵树一一对应,有不一样的就返回false,最后返回True,注意一定是p,q两树,树的左都一样,树的右都一样才可以
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p==null && q==null){
return true;
}
if((p!=null && q==null) || (p==null && q!=null)){
return false;
}
if(p.val!=q.val){
return false;
}
boolean a = isSameTree(p.left,q.left);
boolean b = isSameTree(p.right,q.right);
return a && b;
}
}
2,另一棵树的子树
题目描述:
给你两棵二叉树
root
和subRoot
。检验root
中是否包含和subRoot
具有相同结构和节点值的子树。如果存在,返回true
;否则,返回false
。二叉树
tree
的一棵子树包括tree
的某个节点和这个节点的所有后代节点。tree
也可以看做它自身的一棵子树。
思路:我们使用刚才检查两棵树是否相同的方法,再判断是否为子树的方法中,当两棵树刚开始都为空的时候,那么就是对的,如果,再某个节点树的结构相同时就返回True,root为空返回false,因为没有节点能够和subroot比对了,最后,只要左树和右树存在一个True就是对的
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root==null && subRoot==null){
return true;
}
if(root==null){
return false;
}
if(isSameTree(root,subRoot)){
return true;
}
return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
}
public boolean isSameTree(TreeNode p,TreeNode q){
if(p==null && q==null){
return true;
}
if((p==null && q!=null) || (p!=null && q==null)){
return false;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}
3,翻转二叉树
题目描述:
给你一棵二叉树的根节点
root
,翻转这棵二叉树,并返回其根节点。
思路:仔细看每棵树,我们可以把它当做子问题来处理,递归到每个节点的时候,把它的左右节点调换就可以了。
class Solution {
TreeNode tmp = null;
public TreeNode invertTree(TreeNode root) {
if(root==null){
return root;
}
tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
4,判断一棵树是否为平衡二叉树
题目描述:
给定一个二叉树,判断它是否是平衡二叉树
平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。
思路:这道题,我们要先写出求深度的代码,我们来看着图和代码一起来过一遍。
import java.util.*;
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
return getHight(root)>=0;
}
public int getHight(TreeNode p){
if(p==null){
return 0;
}
int a = getHight(p.left);
if(a<0){
return -1;
}
int b = getHight(p.right);
if(b<0){
return -1;
}
int c= Math.abs(a-b);
if(c<=1 && b>=0){
return a>b?a+1:b+1;
}
else{
return -1;
}
}
}
先看这个从3节点开始,向左走,到9节点,再向左走为空,返回0,a不小于0,向右走为空,c为0,返回1,3的左边为1,向右走,到20,向左走到15,向左为空,返回0,向右走为空,返回0,返回1给20,20节点向右走,为7节点,7向左走为空,返回0,向右走为空返回0,返回1给20,返回2给3,3节点最终返回3;
再看这个图,可以体现-1的作用了,
我们左走到节点2,向左走到节点3,向左走到节点4,向左走到null,返回0,向右走,返回0,3的左返回,3向右走到4节点,4向左走到null,返回0,向右走到null,返回0,3节点右得到1,2节点左得到2,2几点向右走到3节点,3向左走遇到null,返回0,向右走到null,返回0,2节点右得到1,此时差值为1,已经为最大限度了。1节点左得到3,1节点向右递归到2节点,2节点向左走到null,返回0,向右走到null,返回0,1节点右得到1,此时差值为2,不符合,返回-1,如果此时还存在节点的话,都会返回-1,因为已经不满足了,一直返回,如果不是的话还会进行递归,时间很慢。
5,对称二叉树
题目描述:给你一个二叉树的根节点
root
, 检查它是否轴对称。
思路:跟判断二叉树是否相同是一个思路的,我们只需要把,传入的节点改变即可,让p树的左节点和q树的右节点比,p树的右节点和q树的左节点比
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null){
return true;
}
return isSameTree(root.left,root.right);
}
public boolean isSameTree(TreeNode p, TreeNode q){
if(p==null && q==null){
return true;
}
if((p==null && q!=null) || (p!=null && q==null)){
return false;
}
if(p.val!=q.val){
return false;
}
return isSameTree(p.left,q.right) && isSameTree(p.right,q.left);
}
}
6,二叉树的构建以及遍历
题目描述:
编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。
输入描述:
输入包括1行字符串,长度不超过100。
输出描述:
可能有多组测试数据,对于每组数据, 输出将输入字符串建立二叉树后中序遍历的序列,每个字符后面都有一个空格。 每个输出结果占一行。
思路:这个的话就比较难了,我们得到的只有一个前序遍历的字符串,要把字符串变成二叉树,我们要先创建一个节点类来创建节点,创建一个中序遍历的方法,再创建一个创建树的方法,我们先分析一下是怎么把字符串变成一颗树的,
我们遍历输入的字符串,先遇到a,创建节点a,向左递归,遇到b,创建节点b,向左递归,遇到c,创建节点c,向左递归,遇到井号,返回,遇到井号,返回,走到b的右节点,遇到d,创建d接节点》》》》一直走下去。
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
class TreeNode{
char val;
TreeNode left;
TreeNode right;
public TreeNode(char val){
this.val = val;
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextLine()){
String str = in.nextLine();
Main w = new Main();
TreeNode root = w.createTree(str);
w.inorderTree(root);
}
}
static int i = 0;
public TreeNode createTree(String str){
TreeNode root = null;
char a = str.charAt(i);
if(a!='#'){
root = new TreeNode(a);
i++;
root.left = createTree(str);
root.right = createTree(str);
}
else{
i++;
}
return root;
}
public void inorderTree(TreeNode root){
if(root==null){
return;
}
inorderTree(root.left);
System.out.print(root.val+" ");
inorderTree(root.right);
}
}
inorderTree是中序遍历不多说了,重点看创建树,我们看着代码和图一起分析。
传入字符串,我们获取第一个字符a,不为#,创建一个节点,i++,a节点的左边递归,字符为b,不为#,创建新的节点b,i++,b的左边继续递归,字符为c,不为#,创建节点c,节点c的左继续递归,遇到#,i++,返回null,c的右开始递归,遇到#,返回null,返回b的左,开始递归b的右,字符不为#,创建d节点,i++,向左递归,字符不为#,创建节点e,i++,向左递归,字符为空,i++,返回null,e向右走,字符不为null,创建节点g,i++,向左递归,遇到null,i++,返回,向右递归遇到null,i++,返回null,d向右递归,字符不为null,创建节点f,i++,向右、左递归,字符为#,i++,返回null,向右递归,字符为#,i++,返回null,a向右递归字符为#,i++,返回null,树创建完成。
标签:练习题,return,考前,二叉树,TreeNode,null,root,节点 From: https://blog.csdn.net/2301_79083481/article/details/142306581