[Swift]LeetCode872.叶子相似的树|Leaf-SimilarTrees

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

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

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

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

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

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

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100nodes.

请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

举个例子，如上图所示，给定一颗叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

提示：

给定的两颗树可能会有 1 到 100 个结点。

Runtime: 12 ms

Memory Usage: 19 MB

 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 leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         return traverse(root1) == traverse(root2)
17     }
18 
19     func traverse(_ root: TreeNode?) ->String
20     {
21         if root == nil {return String()}
22         if root?.left == nil && root?.right == nil
23         {
24             return String(root!.val) + "-"
25         }
26         return traverse(root?.left) + traverse(root?.right)
27     }
28 }

12ms

 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 leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         var leaves1 : [Int] = []
17         var leaves2 : [Int] = []
18         getLeaves(root1, &leaves1)
19         getLeaves(root2, &leaves2)
20         
21         return isSame(leaves1, leaves2)
22     }
23     
24     func getLeaves(_ root: TreeNode?, _ leaves: inout [Int]) {
25         guard let node = root else {
26             return
27         }
28         if node.left == nil && node.right == nil {
29             leaves.append(node.val)
30             return
31         }
32         getLeaves(node.left, &leaves)
33         getLeaves(node.right, &leaves)
34     }
35     
36     func isSame(_ leaves1: [Int], _ leaves2: [Int]) -> Bool {
37         if leaves1.count != leaves2.count {
38             return false
39         }
40         
41         for i in 0..<leaves1.count {
42             if leaves1[i] != leaves2[i] {
43                 return false
44             }
45         }
46         return true
47     }
48 }

Runtime: 16 ms

Memory Usage: 19.1 MB

 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 leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         if root1 == nil {
17             if root2 == nil {
18                 return true
19             }
20             return false
21         }
22         
23         var roots1: [Int] = [], roots2: [Int] = []
24         
25         traversingBTree(root1!, roots: &roots1)
26         traversingBTree(root2!, roots: &roots2)
27         
28         //    遍历并且存储叶节点的值至数组
29         
30         guard roots1.count == roots2.count else {
31             return false
32         }
33         
34         for index in 0..<roots1.count {
35             if roots1[index] != roots2[index] {
36                 return false
37             }
38         }
39         
40         return true
41     }
42     
43     func traversingBTree(_ root: TreeNode, roots: inout [Int]) {
44         
45         if root.left == nil && root.right == nil {
46             roots.append(root.val)
47             return ;
48         }
49         if let left = root.left {
50             traversingBTree(left, roots: &roots)
51         }
52         
53         if let right = root.right {
54             traversingBTree(right, roots: &roots)
55         }
56     }
57 }

16ms

 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 leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16 
17         return getLeaves(root1) == getLeaves(root2)
18         
19     }
20     func getLeaves(_ root:TreeNode?) -> [Int]
21     {
22         guard let root = root else
23         {
24             return []
25         }
26         var result: [Int] = []
27         if root.left == nil && root.right == nil
28         {
29             result += [root.val]
30         }
31         result += getLeaves(root.left)
32         result += getLeaves(root.right)
33         return result
34     }
35 }

24ms

 1 class Solution {
 2     func leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
 3         var arr1 = [Int]()
 4         var arr2 = [Int]()
 5         helper(root1, &arr1)
 6         helper(root2, &arr2)
 7         for i in 0..<min(arr1.count, arr2.count) {
 8             if arr1[i] != arr2[i] {
 9                 return false
10             }
11         }
12         return true
13     }
14     
15     func helper(_ root: TreeNode?, _ arr: inout [Int]) {
16         guard root?.left != nil || root?.right != nil else {
17             if root != nil {
18                 arr.append(root!.val)
19             }
20             return
21         }
22         helper(root?.left, &arr)
23         helper(root?.right, &arr)
24     }
25 }

28ms

 1 class Solution {
 2     func leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
 3     var arr1 = [Int]()
 4     var arr2 = [Int]()
 5     
 6     getArray(root1, &arr1)
 7     getArray(root2, &arr2)
 8     
 9     return arr1 == arr2
10 }
11     func getArray(_ root: TreeNode?, _ arr: inout [Int]) {
12         guard let r = root else { return }          
13         if r.left == nil && r.right == nil {             
14             arr.append(r.val)
15         } else {
16             getArray(r.left, &arr)
17             getArray(r.right, &arr)
18         }
19     }
20 }

32ms

 1 class Solution {
 2     func leafSimilar(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
 3         var array1: [Int] = []
 4         var array2: [Int] = []
 5         dfs(root: root1, result: &array1)
 6         dfs(root: root2, result: &array2)
 7         return array1 == array2
 8     }
 9     
10     func dfs(root: TreeNode?, result: inout [Int]) -> Void {
11         if let r = root {
12             if r.left == nil && r.right == nil {
13                 result.append(r.val)
14             }
15             dfs(root: r.left, result: &result)
16             dfs(root: r.right, result: &result)
17         }
18     }
19 }