[Swift]LeetCode572.另一个树的子树|SubtreeofAnotherTree

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9852026.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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:

Given tree t:

   4 
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given tree s:

Given tree t:

   4
  / \
 1   2

Return false.

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

给定的树 t：

   4 
  / \
 1   2

返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

给定的树 t：

   4
  / \
 1   2

返回 false。

376ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
16         if s == nil || t == nil {return false}
17         return isSameTree(s,t) || isSubtree(s?.left,t) || isSubtree(s?.right,t)
18     }
19     func isSameTree(_ p: TreeNode?, _ q: TreeNode?) -> Bool
20     {
21         if p == nil
22         {
23             if q == nil
24             {
25                 return true
26             }
27             return false
28         }
29         else if q == nil
30         {
31             return false
32         }
33         return p?.val == q?.val 
34         && isSameTree(p?.left, q?.left) 
35         && isSameTree(p?.right, q?.right)
36     }
37     
38 }

120ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15 func isSameTree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
16     if (s == nil && t != nil) || (s != nil && t == nil) {
17         return false
18     }
19     
20     if s == nil && t == nil {
21         return true
22     }
23     
24     if s!.val != t!.val {
25         return false
26     }
27     
28     return isSubtree(s?.left, t?.left) && isSubtree(s?.right, t?.right)
29 }
30 
31 func getSuitableNode(_ s: TreeNode?, _ dest: Int, _ result: inout [TreeNode?]) -> Int {
32     guard let s = s else {
33         return -1
34     }
35     
36     let depth = max(getSuitableNode(s.left, dest, &result), getSuitableNode(s.right, dest, &result)) + 1
37     if depth == dest {
38         result.append(s)
39     }
40     
41     return depth
42 }
43 
44 func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
45     if s == nil && t == nil {
46         return true
47     }
48     
49     if s == nil || t == nil {
50         return false
51     }
52     
53     var nodes = [TreeNode?]()
54     let depth = getSuitableNode(t, -1, &nodes)
55     
56     getSuitableNode(s, depth, &nodes)
57     
58     for node in nodes {
59         if isSameTree(node, t) {
60             return true
61         }
62     }
63     
64     return false
65 }
66 }

124ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
16         let S = getString(s)
17         let T = getString(t)
18         
19         return S.contains(T)
20     }
21     
22     func getString(_ n: TreeNode?) -> String {
23         guard let n = n else { return "nil" }
24         
25         return "#" + String(n.val) + getString(n.left) + getString(n.right)
26     }
27 }

164ms

 1 class Solution {
 2     func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
 3         guard let t = t else {
 4             return s == nil
 5         }
 6 
 7         if let s = s {
 8             if s.val == t.val {
 9                 return isSameTree(s,t) || isSubtree(s.left,t) || isSubtree(s.right,t)
10             } else {
11                 return isSubtree(s.left,t) || isSubtree(s.right,t)
12             }
13         }
14         return false
15     }
16     
17     func isSameTree(_ s:TreeNode?, _ t:TreeNode?) -> Bool {
18         guard let _s = s, let _t = t else {
19             return s == nil && t == nil
20         }
21         if _s.val != _t.val {
22             return false
23         }
24         
25         return isSameTree(_s.left,_t.left) && isSameTree(_s.right,_t.right)
26     }
27 }

180ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func isSubtree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
16         guard let s = s else {
17             return t == nil
18         }
19         
20         guard let t = t else {
21             return true
22         }
23         
24         let left = isSubtree(s.left, t)
25         let right = isSubtree(s.right, t)
26         return left || right || isSameTree(s, t)
27     }
28     
29     fileprivate func isSameTree(_ s: TreeNode?, _ t: TreeNode?) -> Bool {
30         
31         guard let s = s else {
32             return t == nil
33         }
34         
35         guard let t = t else {
36             return false
37         }
38         
39         let left = isSameTree(s.left, t.left)
40         let right = isSameTree(s.right, t.right)
41         return s.val == t.val && left && right
42     }
43 }