《剑指offer》面试题18 树的子结构 Java版

（输入两棵二叉树A和B，判断B是不是A的子结构。补充下，根据书中的代码来看，子结构的定义并不包括叶子节点下的null，也就是说只要B的存在数字的结构存在于A中就行，那么如果B是null树，那么就不属于A的子结构）

书中方法：书上的方法十分清晰，分为两个步骤，先在A树中找到B树的root.val，然后判断由该点向下是否完全包含B树的结构，直至遍历完A树。

	public boolean isChild(TreeNode aRoot, TreeNode bRoot){

		//A树没有遍历完而且B树不为空

		if(aRoot != null && bRoot != null){

			//在当前节点检查结构，或者去遍历当前节点的左节点或右节点。

			return isQualified(aRoot, bRoot)

					|| isChild(aRoot.left, bRoot)

					|| isChild(aRoot.right, bRoot);

		}

		//A树遍历完了或者B树是个null

		return false;

	}

	private boolean isQualified(TreeNode aRoot, TreeNode bRoot){

		//检查到了B的末尾

		if(bRoot == null)return true;

		//如果在检查完B之前A到了底

		if(aRoot == null)return false;

		//都不是null且val相等，继续检查

		if(aRoot.val == bRoot.val){

			return isQualified(aRoot.left, bRoot.left)

					&& isQualified(aRoot.right, bRoot.right);

		}

		//都不是null但是val不等

		return false;

	}

我的方法：开始检查一下B是否为空，空的话返回false（定义）。aRoot和bRoot是两个根节点，且都可能在自己的根节点和子节点之间转换。开头，如果aRoot.val和bRoot.val相等了，那么继续对各自的子节点进行对比；如果不相等则移动aRoot并和bRoot进行比较。

	public boolean isChildTree(TreeNode aRoot, TreeNode bRoot){

		//定义，如果B树为空，返回false

		if(bRoot == null){

			return false;

		}

		return isChild2(aRoot, bRoot);

	}

	private boolean isChild2(TreeNode aRoot, TreeNode bRoot){

		//如果检查到了B的末尾

		if(bRoot == null)return true;

		//A到了末尾但是B没有

		if(aRoot == null)return false;

		//如果当前节点相同，进行进一步对比；

		//对比的结果可能是false，此时继续向下检查aRoot.left与bRoot、aRoot.right与bRoot

		if(aRoot.val == bRoot.val){

			return (isChild2(aRoot.left, bRoot.left) && isChild2(aRoot.right, bRoot.right))

					|| isChild2(aRoot.left, bRoot)

					|| isChild2(aRoot.right, bRoot);

		}else{//如果当前节点不同，继续向下检查aRoot.left与bRoot、aRoot.right与bRoot

			return isChild2(aRoot.left, bRoot)

					|| isChild2(aRoot.right, bRoot);

		}

	}

巴特西

《剑指offer》面试题18 树的子结构 Java版

最新文章

热门文章