当前位置：首页 > news >正文

子结构判断

news 2025/10/10 3:28:46

子结构判断

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);
}