数据结构和算法-判断一棵二叉树是否为另一颗二叉树的子树

硅谷探秘者 6317 0 0
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树

例1:


                    |                                   |                           
        /-----------10(10)------\               /-------10(10)------\               
        |                       |               |                   |               
/-------5(5)\             /-----15(15)\         5(5)\         /-----15(15)\         
|           |             |           |             |         |           |         
3(3)\       7(7)\         12(12)      18(18)        7(7)      12(12)      18(18)    
    |           |                                                                   
    4(4)        8(8)                                                                

通过比较可知,左边的二叉树是右方的子树

例2:

                    |                              
        /-----------10(10)------\                        |                 
        |                       |                  /-----15(15)\           
/-------5(5)\             /-----15(15)\            |           |           
|           |             |           |            12(12)      18(18)\     
3(3)\       7(7)\         12(12)      18(18)                         |     
    |           |                                                    20(20)
    4(4)        8(8)                               

比较后可知,右方的二叉树不是左方二叉树的子树

编码思路也很简单,就是逐个比较右方的二叉树的每个节点,以及每个分支,是否再左方的二叉树中存在即可。

java测试代码
/**
 * 二叉树结点类
 * @author 硅谷探秘者(jia)
 */
class Node{
	public int data;
	public Node left;
	public Node right;
	public Node(Node left,Node right,int data) {
		this.left=left;
		this.right=right;
		this.data=data;
	}
	public Node(int data) {
		this.data=data;
	}
}
public class A1 {
	public static void main(String[] args) {
		Node root;
	    Node compare;
		/**
		 * 构造第一颗二叉树
		 */
		Node n4=new Node(4);
		Node n8=new Node(8);
		Node n12=new Node(12);
		Node n18=new Node(18);
		Node n3=new Node(null,n4,3);
		Node n7=new Node(null,n8,7);
		Node n5=new Node(n3,n7,5);
		Node n15=new Node(n12,n18,15);
		Node n10=new Node(n5,n15,10);
		root=n10;
		
		/**
		 * 构造第二课二叉树(测试1)
		 */
		Node c3=new Node(3);
		Node c7=new Node(7);
		Node c5=new Node(c3,c7,5);
		/**
		 * 构造第二课二叉树(测试2)
		 */
		Node c_2_8=new Node(8);
		Node c_2_7=new Node(null,c_2_8,7);
		Node c_2_5=new Node(null,c_2_7,5);
		/**
		 * 构造第二课二叉树(测试3)
		 */
		Node c_3_9=new Node(9);
		Node c_3_8=new Node(null,c_3_9,8);
		Node c_3_7=new Node(null,c_3_8,7);
		/**
		 * 构造第二课二叉树(测试4)
		 */
		Node c_4_20=new Node(20);
		Node c_4_12=new Node(12);
		Node c_4_18=new Node(null,null,18);
		Node c_4_15=new Node(c_4_12,c_4_18,15);
		/**
		 * 构造第二课二叉树(测试5)
		 */
		Node c_5_6=new Node(6);
		Node c_5_7=new Node(c_5_6,null,7);
		Node c_5_5=new Node(null,c_5_7,5);
		Node c_5_12=new Node(12);
		Node c_5_18=new Node(18);
		Node c_5_15=new Node(c_5_12,c_5_18,15);
		Node c_5_10=new Node(c_5_5,c_5_15,10);
		
		compare=c_5_10;
		/**
		 * 层次遍历
		 */
		boolean c=pre(root,compare);
		System.out.println(c);
	}
	
	/**
	 * 先序遍历
	 * head 主二叉树
	 * compare 要比较的子树
	 */
	public static boolean pre(Node head,Node compare) {
		if(head!=null) {
			if(preCompare(head,compare))
				return true;
			if(head.left!=null) 
				if(pre(head.left,compare))
					return true;
			if(head.right!=null)
				if(pre(head.right,compare))
					return true;
		}
		return false;
	}
	/**
	 * 先序遍历子树进行比较
	 */
	public static boolean preCompare(Node h,Node c) {
		if(h!=null&&c!=null) {
			boolean b=true;
			if(h.data!=c.data)
				return false;
			if(c.left!=null&&h.left==null)
				return false;
			if(h.left!=null&&c.left!=null)
				 if(!preCompare(h.left,c.left))
					 return false;
			if(c.right!=null&&h.right==null)
				return false;
			if(h.right!=null&&c.right!=null)
				b = preCompare(h.right,c.right);
			return b;
		}else {
			return false;
		}
	}
}

 

猜你喜欢
数据结构与算法 4722 试题描述:思路:用组表示完全,用先序遍历方式遍历每节点,用组储存每,因规模小于100000所以用个容量17组即可。计完每,再比较层最小之最大
official 174 leetcode第110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定高度平衡
weblog 2983 什么前驱节点后继节点?某节点前驱节点val值小于该节点val值并且值最大那个节点。某节点后继节点val值大于该节点val值并且值最小那个节点。下面给出节点类
数据结构与算法 4115 整理遍历-(递归(非递归)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//
数据结构与算法 7234 )java代码实现importjava.util.LinkedList;/***点类*@author硅谷探秘者(jia)*/classNode{ publicintdata; publicNodele
official 155 个head个节点链表。如果在中,存在直向下路径,且每个点值恰好对应以head链表中每个节点值,那么请你返回True,则返回False。直向下路径意思
数据结构与算法 2459 转载:https://www.cnblogs.com/willwu/p/6007555.html1.定义,它由n(n=1)个有限节点组成个具有层次关系集合。把它叫做“
official 179 径。说明:叶节点指没有节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶节点路径:1-2-5,1-3解题思路递归得方式遍历(深度优先搜索),
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议
目录
祝愿神州十三飞行乘组平安归来