17.树的子结构

题目

输入两棵二叉树A，B，判断B是不是A的子结构。（约定空树不是任意一个树的子结构）。

思路

本题考察递归，
首先判断B是否刚好等于A，
然后判断B是否是A的左子树的子结构，B是否是A的右子树的子结构

在判断是否相等的过程中，同样用到了递归。 因此需要写两个递归方法。
首先判断A、B节点值是否相同，然后判断A、B的左孩子节点值是否相同，并依次递归下去。

代码

public class HasSubTree {
	public boolean hasSubTree(TreeNode root1,TreeNode root2) {
		if(root1 == null || root2 == null) return false;
		return isSubTree(root1,root2) || hasSubTree(root1.left,root2) || hasSubTree(root1.right,root2);
	}

	private boolean isSubTree(TreeNode a, TreeNode b) {
		if(b == null) return true;//先于a判断
		if(a == null) return false;
		if(a.val == b.val) {
			return isSubTree(a.left, b.left) && isSubTree(a.right,b.right);
		}
		return false;
	}
}