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

硅谷探秘者 6599 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;
		}
	}
}