Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Example 1:
Given tree s:3 / 4 5 / 1 2Given tree t:
4 / 1 2Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:3 / 4 5 / 1 2 / 0Given tree t:
4 / 1 2Return false.
另一个树的子树。
题意是给两个树s和t,判断t是否是s的子树。如果s和t相同,也可以视为t是s的子树。
这个题的思路跟100题same tree非常像。既然是问t是否是s的子树,那也就意味着s这棵树比t要大,或者最多相同,所以就可以按照100题的思路递归比较
- s的左子树和右子树是否分别和t一样
- s是否和t是相同的树
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public boolean isSubtree(TreeNode s, TreeNode t) { 3 if (s == null) { 4 return false; 5 } 6 if (isSame(s, t)) { 7 return true; 8 } 9 return isSubtree(s.left, t) || isSubtree(s.right, t); 10 } 11 12 private boolean isSame(TreeNode s, TreeNode t) { 13 if (s == null && t == null) { 14 return true; 15 } 16 if (s == null || t == null) { 17 return false; 18 } 19 if (s.val != t.val) { 20 return false; 21 } 22 return isSame(s.left, t.left) && isSame(s.right, t.right); 23 } 24 }
JavaScript实现
1 /** 2 * @param {TreeNode} s 3 * @param {TreeNode} t 4 * @return {boolean} 5 */ 6 var isSubtree = function (s, t) { 7 if (s == null) { 8 return false; 9 } 10 if (isSameTree(s, t)) { 11 return true; 12 } 13 return isSubtree(s.left, t) || isSubtree(s.right, t); 14 }; 15 16 var isSameTree = function (s, t) { 17 if (s && t) { 18 return s.val === t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right); 19 } 20 return s === t; 21 }
相关题目