先是原始解法,采用递归的方式,代码如下:
class Solution { public boolean isSameTree(TreeNode s, TreeNode t){ if(s == null && t == null) return true; if(s == null || t == null) return false; return s.val == t.val && isSameTree(s.left,t.left) && isSameTree(s.right, t.right); } public boolean isSubtree(TreeNode s, TreeNode t) { if(s == null && t!= null) return false; if(s != null && t == null) return true; else return isSameTree(s,t) || isSubtree(s.left,t) || isSubtree(s.right, t); } }
时间复杂度O(m*n),空间复杂度O(h),h为树的高度。
上面的方法首先要遍历s的每个节点,对于每个节点,t都要遍历一次。
但是,对比两棵树是否相同,不需要一个个节点对比,而是大家有一个唯一标识拿出来对比,这样对比就需要O(1)的时间。比如可以采用把左节点,根结点,右节点的值拼接起来。因此可以采用字符串的hash函数,把整棵树的对比降到O(1)复杂度。因为在构造hash表的时候需要分别遍历一次s和t,所以算法的时间复杂度是O(m+n), 空间复杂度:由于要保存hash表,所以也是O(m+n);
代码如下:
class Solution { Map<TreeNode, Integer> map = new HashMap<>(); public String computeHash(TreeNode s){ if(s == null) return "#"; String left = computeHash(s.left); String right = computeHash(s.right); String hash = left + s.val + right; map.put(s,hash.hashCode()); return hash; } //构建计算hash函数的时候有技巧,要返回字符串的形式便于递归的过程中返回值。 public boolean isSub(TreeNode s, TreeNode t){ if(s == null) return false; if(t == null) return true; return map.get(s).equals(map.get(t)) || isSub(s.left,t ) || isSub(s.right, t); } public boolean isSubtree(TreeNode s, TreeNode t) { computeHash(s); computeHash(t); return isSub(s,t); } }