LeetCode刷题之旅【算法篇】（简单 -6）：572. 另一个树的子树

LeetCode刷题之旅【算法篇】（简单 -6）：572. 另一个树的子树

目录

​​题目：另一个树的子树​​

​​解题1：字符串比较法​​

​​性能​​

​​算法​​

​​复杂度分析​​

​​解题2：遍历子节点​​

​​性能​​

​​算法​​

​​解法3：使用hash比较两棵树​​

​​性能​​

​​算法​​

题目：另一个树的子树

解题1：字符串比较法

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { /**结点值前缀 */ private final static String PRE_FIX = "#"; /**左节点空 */ private final static String LEFT_NULL = "lnull"; /**右节点空 */ private final static String RIGHT_NULL = "rnull"; public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null && t == null){ return true; } String parentTreeString = convertToString(s); String subTreeString = convertToString(t); if ("".equals(subTreeString)){ return false; } return parentTreeString.contains(subTreeString); } private String convertToString(TreeNode s) { StringBuffer result = new StringBuffer(); if (s!=null){ //前序遍历（根-左子树-右子树） result.append(PRE_FIX + s.val); if (s.left != null){ result.append(convertToString(s.left)); } else { result.append(LEFT_NULL); } if (s.right != null){ result.append(convertToString(s.right)); } else { result.append(RIGHT_NULL); } } return result.toString(); }}

性能

算法

我们可以找到给定树 ss 和 tt 的先序遍历序列，分别由 ss 先序遍历和 tt 先序遍历给出（以字符串形式表示）。现在，我们可以检查 tt 先序遍历序列是否是 ss 先序遍历序列的子字符串。

但是，为了使用这种方法，我们需要以不同的方式处理给定的树。我们不需要为空叶节点假定 nullnull 值，而是需要分别将空左子节点和空右子节点视为 lnulllnull 和 rnullrnull 值。

还可以注意到，我们在考虑每个值之前都添加了一个 “#”。如果不这样做，形式 s:[23, 4, 5] 和 t:[3, 4, 5] 的树也将给出一个 true 的结果，因为 t 的先序遍历字符串 (“23 4 lnull rnull 5 lnull rnull”) 将是 s 的先序遍历字符串 (“3 4 lnull rull 5 lnull rnull”) 的子字符串。在节点值之前添加一个 “#” 可以解决这个问题。

复杂度分析

时间复杂度：O(m^2+n^2+mn)O(m 2 +n 2 +mn)。空间复杂度：max(m,n)max(m,n)，在最坏的情况下，递归树的深度可以达到树 tt 的 nn 和树 ss 的 mm 之间。

解题2：遍历子节点

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public boolean isSubtree(TreeNode s, TreeNode t) { return findSubtree(s,t,t); } public boolean findSubtree(TreeNode s, TreeNode t, TreeNode orit) { if(t!=null && s!=null) { if(s.val == t.val) { // || 判断是给根节点一样，但后续不一样的情况再次判断的机会。此处写得比较粗糙。 // 可以改进（用flag变量） return (findSubtree(s.left, t.left, orit) && findSubtree(s.right, t.right, orit)) || (findSubtree(s.right,t,orit) || findSubtree(s.left,t,orit)); } else { return findSubtree(s.left, orit,orit) ||findSubtree(s.right, orit,orit); } } else if(t==null && s==null) { return true; } else { return false; } }}

性能

算法

递归（注意几个特殊条件）特殊条件一：根节点一样，但后续不一样。进入判定流程，若判定失败；则要放弃该根节点，进入下一个，不能直接return false；特殊条件二：根节点不一样，进入左右子树进行新的判断，此时的t指针一定要重新指向t树原始根节点

解法3：使用hash比较两棵树

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { private boolean isSub = false; public boolean isSubtree(TreeNode s, TreeNode t) { // 计算目标子树的hash值 int hash = hash(t); int i = hashT(s, hash, t); if (i == hash) { return checkNode(s, t); } return isSub; } /** * 检查树的节点 */ private boolean checkNode(TreeNode node1, TreeNode node2) { if (node1 == null && node2 == null) { return true; } if (node1 == null || node2 == null) { return false; } if (node1.val != node2.val) { return false; } return checkNode(node1.left, node2.left) && checkNode(node1.right, node2.right); } /** * 递归计算节点的hash值 */ private int hash(TreeNode node) { if (node == null) { return 0; } return hash(node.left) + hash(node.right) + node.val; } private int hashT(TreeNode node, int hash, TreeNode t) { if (node == null) { return 0; } //计算源树的hash值 int hashCur = hashT(node.left, hash, t) + hashT(node.right, hash, t) + node.val; if (hashCur == hash) { boolean check = checkNode(node, t); if (check) { isSub = true; } } return hashCur; }}

性能

算法

计算 TreeNode t 的 hash 值 a1递归计算 TreeNode s 的 hash 值 a2, 如果 a1 == a2 则检查两颗子树是否相同优势: 在某些应用中, 能大量减少比较次数, 选用不同的hash函数, 可以达到不同的效果劣势:比较复杂的解决方法

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。