《剑指offer》– 树的子结构、二叉树的镜像、二叉树的深度、平衡二叉树

《剑指offer》– 树的子结构、二叉树的镜像、二叉树的深度、平衡二叉树

一、 树的子结构:

1、题目:

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构。

2、解题思路:

这个题比较简单,利用递归的方式就可以判断B是不是A树的子结构。

3、实现代码:

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
		//当tree1和tree2都不为空的时候,才进行比较。否则直接返回false
		if(root1 ==null || root2 == null){
			return false;
		}
		
		以这个根节点为、根节点左子树、右子树 为起点判断是否包含Tree2
		return (isSubtree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right, root2));
    }


	private boolean isSubtree(TreeNode root1, TreeNode root2) {
		//以下两个if的顺序不能调换
		//如果tree2已经遍历完了,表示都可以对应上,返回true
		if(root2==null)
			return true;
		//如果tree2已经遍历完,tree1还没遍历完,返回false
		if(root1==null)
			return false;
		
		//如果根节点对应的上,那么就分别去子节点里面匹配
		if(root1.val ==root2.val){
			return (isSubtree(root1.left,root2.left) && isSubtree(root1.right, root2.right));
		}else{
			return false;
		}
	}

 

 

二、二叉树的镜像:

1、题目:

操作给定的二叉树,将其变换为源二叉树的镜像。

2、输入描述:

二叉树的镜像定义:源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

3、解决思路:

采用递归的方式,递归交换每一个父节点的两个子节点的位置。

4、实现代码:

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)
            return ;
         if(root.left==null && root.right==null)
           return;
       
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        
        Mirror(root.left);
        Mirror(root.right);
    }
}

 

 

三、二叉树的深度:

1、题目:

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

2、解决思路:

递归方式和层序遍历方式都可以解决。

3、代码实现:

public class Test3 {
	
	//第二种:非递归方式:层序遍历:
	public int TreeDepth(TreeNode root) {
		if(root == null){
			return 0;
		}
		
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		//depth代表当前节点所在的层数,count代表已经遍历的节点数,nextCount代表下一层的节点数
		//当count==nextCount的时候,代表本次节点已经遍历完毕
		int depth=0,count=0,nextCount=1;
		
		while(queue.size()!=0){
			count++;
			TreeNode top = queue.poll();
			if(top.left!=null){
				queue.add(top.left);
			}
			if(top.right!=null){
				queue.add(top.right);
			}
			
			if(count==nextCount){
				depth++;
				count=0;
				nextCount=queue.size();
			}
		}
		return depth;
    }
	
	//第一种:递归方式
	public int TreeDepth1(TreeNode root) {
		if(root == null){
			return 0;
		}
		int left= TreeDepth1(root.left);
		int right =TreeDepth1(root.right);
		
		return Math.max(left, right)+1;
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

 

 

四、平衡二叉树:

1、题目:

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

2、解题思路:

递归方式或者后序遍历的方式都可以解决。

3、代码实现:

public class Test5 {
	
	private boolean isBalanced = true;
	//第三种:后续遍历时,遍历到一个节点,其左右子树已经遍历  依次自底向上判断,每个节点只需要遍历一次
	public boolean IsBalanced_Solution2(TreeNode root) {
		getDepth2(root);
		return isBalanced;
	}
	
	public int getDepth2(TreeNode root){
		if(root == null){
			return 0;
		}
		int left=getDepth2(root.left);
		int right=getDepth2(root.right);
		
		if(Math.abs(left-right)>1){
			isBalanced=false;
		}
		return Math.max(left, right)+1;
	}
	
	
	//第二种方法:三种中最好的方式
	//如果改为从下往上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,
	//则直接停止遍历,这样至多只对每个结点访问一次。
	public boolean IsBalanced_Solution1(TreeNode root) {
		return getDepth(root) !=-1;
	}
	
	public int getDepth(TreeNode root){
		if(root == null) return 0;
		int left=getDepth(root.left);
		if(left == -1 ) return -1;
		int right=getDepth(root.right);
		if(right == -1) return -1;
		
		return Math.abs(left-right)>1?-1:1+Math.max(left, right);
	}
	
	
	//第一种方法:递归方式
	//这种做法有很明显的问题,在判断上层结点的时候,会多次重复遍历下层结点,增加了不必要的开销。
	 public boolean IsBalanced_Solution(TreeNode root) {
		 if(root == null){
			 return true;
		 }
		 return Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1
		 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }
	 
	 private int maxDepth(TreeNode root){
		 if(root == null){
			 return 0;
		 }
		 return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
	 }
}


class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114698.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java删除文件目录及文件_Java删除文件,目录

    java删除文件目录及文件_Java删除文件,目录java删除文件目录及文件TodaywewilllookintoJavadeletefileandjavadeletedirectoryexamples.Earlierwelearnedhowtocreateafileinjava.今天,我们将研究Java删除文件和Java删除目录示例。之前我们学习了如何在java中创建文件。Java删除文件…

  • navicat 中文注册码「建议收藏」

    navicat 中文注册码「建议收藏」中文版Navicatmysql9.x下载地址:http://download2.navicat.com/download/navicat091_mysql_cs.exe下载地址:http://download2.navicat.com/download/navicat091_mysql_cs.tar.gz注册码:NAVL-KSG4-K8D8-8TV6中文版Navicatm…

    2022年10月13日
  • Github项目解析(九)–>实现Activity跳转动画的五种方式

    Github项目解析(九)–>实现Activity跳转动画的五种方式文本中我们将讲解activity切换动画相关的知识点,这里的切换动画指的是是activity跳转时的动画效果。这里总结了一下,有五种方式实现activity切换时实现动画效果。下面我将依次介绍一下每种实现activity切换动画效果的实现方式

  • 程序员的生存法则_程序员的一生

    程序员的生存法则_程序员的一生前几天,和国内某知名企业的行销一线喝茶聊天,他一直在抱怨自己的上司很差劲,一直允诺追加奖金,但是月底考评结果却给的很差,奖金也没别人的多,所以他想调别的部门。我很是惊诧,这公司是你们家开的?怎么可以想调就调?他笑了笑说,你不懂职场生存法则吗?    他的工作需要经常出差,全国各地跑。上次是去江西,他知道部门A的老大老家在江西,就主动去找A部门老大,告之有个出差机会,要不要一起?后来我才明白“要不

  • 批处理 %~0_批处理输入

    批处理 %~0_批处理输入%~dp0“d”为Drive的缩写,即为驱动器,磁盘、“p”为Path缩写,即为路径,目录cd是转到这个目录,不过我觉得cd/d%~dp0还好些%~dp0“d”为Drive的缩写,即为驱动器,磁盘、“p”为Path缩写,即为路径,目录cd是转到这个目录,不过我觉得cd/d%~dp0还好些选项语法:~0-删除任何引号(“),扩充%

  • qt tcpsocket_qt的socket通信

    qt tcpsocket_qt的socket通信QTcpSocket类的方法connectToHost会泄露内存,即使把调用这个方法的QTcpSocket实例delete掉,内存也不会释放!反复connectToHost会导致段错误,十分危险。必须控制connectToHost的使用次数!连接服务器m_tcpSocket->connectToHost(“127.0.0.1”,9877);connected=m_tcpSocket-

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号