剑指--树的子结构

剑指–树的子结构

1，题目：

2，思路：

写法二中的代码写的更便于理解。看写法二：

解题思路： 1.若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：

2.先序遍历树 A 中的每个节点 n_A；（对应函数 isSubStructure(A, B)） 3.判断树 A 中 以 n_A为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）

recur(A, B) 函数：

1.终止条件： 2.当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ； 3.当节点 A为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ； 4.当节点 A和 B 的值不同：说明匹配失败，返回 false ； 5.返回值： 6.判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ； 7.判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ；

isSubStructure(A, B) 函数：

1.特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ； 2.返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接； 3.以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)； 4.树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)； 5.树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；

3，代码：

class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { /* 解题思路： 1.若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作： 2.先序遍历树 A 中的每个节点 n_A；（对应函数 isSubStructure(A, B)） 3.判断树 A 中 以 n_A为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)） recur(A, B) 函数： 1.终止条件： 2.当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ； 3.当节点 A为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false ； 4.当节点 A和 B 的值不同：说明匹配失败，返回 false ； 5.返回值： 6.判断 A 和 B 的左子节点是否相等，即 recur(A.left, B.left) ； 7.判断 A 和 B 的右子节点是否相等，即 recur(A.right, B.right) ； isSubStructure(A, B) 函数： 1.特例处理： 当 树 A 为空 或 树 B 为空 时，直接返回 false ； 2.返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接； 3.以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)； 4.树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)； 5.树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)； */ return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); } 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); } }

写法二：思路是一样的：

class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { if (B == null || A == null) { return false; } if (A.val == B.val && (helper(A.left, B.left) && helper(A.right, B.right))) { return true; } return isSubStructure(A.left, B) || isSubStructure(A.right, B); } private boolean helper(TreeNode root1, TreeNode root2) { if (root2 == null) { return true; } if (root1 == null) { return false; } if (root1.val == root2.val) { return helper(root1.left, root2.left) && helper(root1.right, root2.right); } else { return false; } } }