25. 이 진 트 리 두 개 를 입력 하여 B 트 리 가 A 트 리 의 하위 구조 인지 판단

9788 단어 데이터 구조
package java2019;
//       ,  B    A     
public class Demo25 {
	public static boolean HasSubtree(TreeNode root1,TreeNode root2){
		boolean result = false;
		// Tree1 Tree2   null,     。      false
		if(root2!=null && root1!=null){
			//       Tree2      
			if(root1.val==root2.val){
				//               Tree2
				result = doseTree1HaveTree2(root1,root2);
			}
			//     ,     root        ,       Tree2
			if(!result){
				result = HasSubtree(root1.left,root2);
			}
			//      ,     root        ,       Tree2
			if(!result){
				result = HasSubtree(root1.right,root2);
			}
		}
		//    
		return result;
	}
	
	public static boolean doseTree1HaveTree2(TreeNode node1,TreeNode node2){
		//  Tree2            ,  true
		if(node2 == null){
			return true;
		}
		//  Tree2      ,Tree1     。  false
		if(node1 == null){
			return false;
		}
		//             ,  false
		if(node1.val!=node2.val){
			return false;
		}
		//         ,             
		return doseTree1HaveTree2(node1.left,node2.left) &&
				doseTree1HaveTree2(node1.right,node2.right);
	}
	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(5);
		TreeNode n1 = new TreeNode(3);
		TreeNode n2 = new TreeNode(10);
		TreeNode n3 = new TreeNode(1);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(6);
		TreeNode n6 = new TreeNode(11);
		
		root1.left=n1;
		root1.right=n2;
		n1.left=n3;
		n1.right=n4;
		n2.left=n5;
		n2.right=n6;
		System.out.println(HasSubtree(root1,n5));
	}

}

좋은 웹페이지 즐겨찾기