《剑指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)


相关推荐

  • swoole高性能赛事直播平台(笔记)

    swoole高性能赛事直播平台(笔记)

  • 腾讯淘宝网_新浪业务

    腾讯淘宝网_新浪业务From:http://blog.csdn.net/perfect2011/article/details/18844575

  • 官网下载mysql连接驱动jar包教程「建议收藏」

    官网下载mysql连接驱动jar包教程「建议收藏」1.网址上输入mysql.com后回车2.点击如图所示3.滑下来找到如图所示并点击4.进来后,点击如图所示5.选择不同版本5.1下载最新版本的,如图按步骤点击5.2下载其他版本点击这个6.点击后下载第二个7.点击后,点击如下,几秒后即可完成下载,(有时候第6步就直接下载了,就不需要这步了)8.下载完后解压,找到如下文件,这就是ja…

  • android自定义滑块解锁,android 滑动解锁

    android自定义滑块解锁,android 滑动解锁通过android自定义View实现横向的滑动解锁,1、滑动到中间会自动返回到原始的位置,2、滑动到底部会自动解锁,会触发解锁的回调;首先看效果图如下:实现以上部分一共分为三部分:其中背景通过shape.xml实现滑动的锁是一张图片文字通过Paint绘制在中间,高度可定制主要介绍一下实现的主要部分:(1)有自定义的属性如下:(2)重写ondraw()方法,绘制文字和锁:@Overrideprote…

  • jdbc和数据库连接池_常用的数据库连接池

    jdbc和数据库连接池_常用的数据库连接池数据库连接池JDBC数据库连接池的必要性在使用开发基于数据库的web程序时,传统的模式基本是按照以下步骤:在主程序(如servlet beans)中建立数据库连接进行sql操作断开数据库连接这种模式开发,存在的问题:普通的JDBC数据库连接使用DriverManager来获取,每次向数据库建立连接的时候都要将Connection加载到内存中,再验证用户名和密码(大概花费0.05s-1s),需要数据库连接的时候,就向数据库要求一个,执行完成后再断开。这样的方式将会消耗大量的时间。数据库的

  • sql2005置疑数据库修复_sqlserver2008数据库可疑

    sql2005置疑数据库修复_sqlserver2008数据库可疑–修改数据库为紧急模式alterdatabaseP897A20_dbsetemergency–但用户模式alterdatabaseP897A20_dbsetsingle_user–修复数据库日至dbcccheckdb(P897A20_db,repair_allow_data_loss)–恢复多用户模式alterdatabaseP89

发表回复

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

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