子结构判断
LCR 143. 子结构判断
参考题解
题前知识
1)子结构
首先我们先了解一下子结构:
- 原题信息:判断
tree2
是否以tree1
的某个节点为根的子树具有 相同的结构和节点值 。 - 子结构也就是
B
树是否含于A
树左子树或者右子树之中,并且具有相同的结构和节点值,或者是否以A
树的根节点作为子树
2)先序遍历
该题使用到了先序遍历,先序遍历相关代码
先序遍历规则:根左右
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();dfs(res, root);return res;
}
private void dfs(List<Integer> res, TreeNode root){if(root == null){return;}res.add(root.val);dfs(res, root.left);dfs(res, root.right);}
正题
我们可以使用先序遍历树A
的每个节点,然后我们判断A
树是否包含B
树
由于我们判断A
树是否包含B
树是从根节点开始匹配的,所以先序遍历的更合适本题
判断A
树是否包含B
树
终止条件
B
为空,说明B
已经匹配完成,返回true
;A
为空,匹配失败,B
树已经越过了A
的叶子结点,超出范围了,返回false
;A
的节点值和B
的节点值不一样,返回false
返回条件
- 判断
A
的左节点是否和B
的左节点相等 –>recur(A.left, B.left)
- 判断
A
的右节点是否和B
的右节点相等 –>recur(A.right, B.right)
public boolean recur(TreeNode A, TreeNode B) {if(B == null) return true;if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);
}
isSubStructure(A, B)
函数
边界条件
A
树或者B
树为null
,返回false
三种情况
- 以
A
的根节点为子树包含B
- 以
A
的左子树为子树包含B
- 以
A
的右子树为子树包含B
以上情况只要符合一种就返回true
最终代码:
通过recur(A, B)
找到B
的根节点和B
的子节点是否和A
的匹配
public boolean isSubStructure(TreeNode A, TreeNode B) {return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}public boolean recur(TreeNode A, TreeNode B) {if(B == null) return true;if(A == null || A.val != B.val) return false;return recur(A.left, B.left) && recur(A.right, B.right);
}
题后解析
关于题中用到的先序遍历思想
1、isSubStructure(A, B)
中的先序遍历
对于树A的某个节点:
- 先访问根节点:执行
recur(A, B)
检查当前节点是否能作为匹配的起点 - 再遍历左子树:如果根节点不匹配,递归调用
isSubStructure(A.left, B)
- 最后遍历右子树:如果左子树也没有找到,递归调用
isSubStructure(A.right, B)
2、recur
方法中的先序遍历
- 先比较当前根节点的值 (
A.val != B.val
) - 再递归比较左子树 (
recur(A.left, B.left)
) - 最后递归比较右子树 (
recur(A.right, B.right)
)