题目链接

牛客在线oj题——树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000

题目示例

示例1

输入：
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

返回值：
true

示例2

输入：
{1,2,3,4,5},{2,4}

返回值：
true

示例3

输入：
{1,2,3},{3,1}

返回值：
false

解题思路

首先，要判断一个二叉树是否是另外一个二叉树的子树，就需要判断两颗树是否完全一样

那么先介绍一下判断两棵树完全一样的方法：如果root2 == null，说明已经递归到root2的尽头了，返回true

如果root1为空，此时root2肯定不为空，那么说明root1和root2不相等，返回false

分别判断root1.left和root2.left是否相等，root1.right和root2.right是否相等，两者都相等返回true，否则返回false

接下来介绍如何判断root2是否为root1的子结构，如果root1或者root2为空，题目中说到空树不是任意一个树的子结构，直接返回false

然后判断root1.val和root2.val是否相等，如果相等则开始用上面介绍的方法比较root1和root2是否相等

否则的话就递归root1.left和root2是否相等，root1.right和root2是否相等，只要有一个相等就返回true

完整代码

/
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public boolean HasSubtree(TreeNode root1,TreeNode root2) {if(root1 == null || root2 == null){return false;}boolean result = false;if(root1.val == root2.val){result = isSameChild(root1, root2);}if(!result){result = HasSubtree(root1.left, root2);}if(!result){result = HasSubtree(root1.right, root2);}return result;}/* 判断左右子树是否相等* @param root1* @param root2* @return*/private boolean isSameChild(TreeNode root1, TreeNode root2) {if(root2 == null){return true;}if(root1 == null){return false;}if(root1.val != root2.val){return false;}return isSameChild(root1.left, root2.left) && isSameChild(root1.right, root2.right);}
}