题意

判断一棵树(参数二)是不是另一棵树(参数一)的子结构。

题解

递归第一棵树，找两棵树中值一样的节点。若找到后，用另一个函数判断以相同值得节点为根的树2是不是树1的子结构。

代码

class TreeNode{

	double val;

	TreeNode lChild;

	TreeNode rChild;

	TreeNode(double val){

		this.val=val;

	}

}

public class Main {

	public static void main(String[] args) {

		//test case

		TreeNode node1=new TreeNode(1);

		TreeNode node2=new TreeNode(2);

		TreeNode node3=new TreeNode(3);

		node1.lChild=node2;

		node1.rChild=node3;

		TreeNode node4=new TreeNode(4);

		TreeNode node5=new TreeNode(1);

		TreeNode node6=new TreeNode(2);

		TreeNode node7=new TreeNode(3);

		node4.lChild=node5;

		node5.lChild=node6;

		node5.rChild=node7;

		if(hasSubTree(node4,node1)) {

			System.out.print("true");

		}

		else {

			System.out.print("false");

		}

	}

	public static boolean hasSubTree(TreeNode root,TreeNode subTreeRoot) {

		 if(subTreeRoot==null) {

			 return true;

		 }

		 if(root==null) {

			 return false;

		 }

		 boolean ans=false;

		 if(equal(root.val,subTreeRoot.val)) {//根节点相同才开始判所在的两棵子树是否相同

			 ans=tree1HasTree2(root,subTreeRoot);

		 }

		 if(!ans) {//

			 ans=hasSubTree(root.lChild,subTreeRoot);

		 }

		 if(!ans) {

			 ans=hasSubTree(root.rChild,subTreeRoot);

		 }

		 return ans;

	}

	public static boolean tree1HasTree2(TreeNode root1,TreeNode root2) {

		if(root2==null) {

			return true;

		}

		if(root1==null) {

			return false;

		}

		if(!equal(root1.val,root2.val)) {//递归过程中每次判断节点相同

			return false;

		}

		return tree1HasTree2(root1.lChild,root2.lChild)&&tree1HasTree2(root1.rChild,root2.rChild);

	} 

	public static boolean equal(double num1,double num2) {

		return Math.abs(num1-num2)<0.0000001;

	}

}