[Swift]LeetCode951.翻转等价二叉树|FlipEquivalentBinaryTrees

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

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

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

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

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

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

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:

Input: root1 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Note:

Each tree will have at most 100 nodes.
Each value in each tree will be a unique integer in the range [0, 99].

我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。

编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1和 root2 给出。

示例：

输入：root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出：true
解释：We flipped at nodes with values 1, 3, and 5.

提示：

每棵树最多有 100 个节点。
每棵树中的每个值都是唯一的、在 [0, 99] 范围内的整数。

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 flipEquiv(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         if root1 == nil {return root2 == nil}
17         if root2 == nil {return root1 == nil}
18         if root1!.val != root2!.val {return false}
19         if flipEquiv(root1!.left, root2!.left) && flipEquiv(root1!.right, root2!.right)
20         {
21             return true
22         }
23         if flipEquiv(root1!.left, root2!.right) && flipEquiv(root1!.right, root2!.left)
24         {
25             return true
26         }
27         return false
28     }
29 }

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 flipEquiv(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         if root1 == nil && root2 == nil {
17             return true
18         }
19         guard let root1 = root1, let root2 = root2 else {
20             return false
21         }
22         guard root1.val == root2.val else {
23             return false
24         }
25         return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) || (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))
26     }
27 }

20ms

 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 flipEquiv(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         if root1 == nil && root2 == nil { return true }
17         if (root1 != nil && root2 == nil) || (root1 == nil && root2 != nil) {return false}
18         
19         var root1 = root1
20         
21         var level1:  [TreeNode?] = [root1]
22         var level2:  [TreeNode?] = [root2]
23         var level1n:  [TreeNode?] = []
24         var level2n:  [TreeNode?] = []
25         var rr = 0
26         while level1.count > 0 {
27             if level1.count != level2.count { return false }
28             print(rr)
29             rr += 1
30             if level1.count == 1 {
31                 if level1[0] == nil && level2[0] != nil { return false }
32                 if level1[0] != nil && level2[0] == nil { return false }
33                 if level1[0] == nil && level2[0] == nil { continue }
34                 if level1[0]?.val != level2[0]?.val { return false }
35             } else {
36                 var i = 0
37                 while i < level1.count - 1 {
38                     defer { i += 2 }
39                     if level1[i] == nil && level2[i] == nil && level1[i+1] == nil && level2[i+1] == nil { continue }
40                     if level1[i] != nil && level2[i] != nil && level1[i]?.val == level2[i]?.val && level1[i+1] != nil && level2[i+1] != nil && level1[i+1]?.val == level2[i+1]?.val { continue }
41                     
42                     if level1[i] != nil && level2[i] != nil && level1[i+1] == nil && level2[i+1] == nil && level1[i]?.val == level2[i]?.val { continue }
43                     
44                     if level1[i] == nil && level2[i] == nil && level1[i+1] != nil && level2[i+1] != nil && level1[i+1]?.val == level2[i+1]?.val { continue }
45                     
46                     if level1[i] != nil && level2[i] != nil && level1[i+1] != nil && level2[i+1] != nil && level1[i]?.val == level2[i+1]?.val {
47                         var tmp = level1[i]
48                         level1[i] = level1[i+1]
49                         level1[i+1] = tmp
50                         continue
51                     }
52                     if level1[i] != nil && level2[i] == nil && level1[i+1] == nil && level2[i+1] != nil && level1[i]?.val == level2[i+1]?.val {
53                         var tmp = level1[i]
54                         level1[i] = level1[i+1]
55                         level1[i+1] = tmp
56                         continue
57                     }
58                     
59                     if level1[i] == nil && level2[i] != nil && level1[i+1] != nil && level2[i+1] == nil && level1[i+1]?.val == level2[i]?.val {
60                         var tmp = level1[i]
61                         level1[i] = level1[i+1]
62                         level1[i+1] = tmp
63                         continue
64                     }
65                     
66                     return false
67                 }
68             }
69             
70             for node in level1 {
71                 if let node = node {
72                     level1n.append(node.left)
73                     level1n.append(node.right)
74                 }
75             }
76             
77             for node in level2 {
78                 if let node = node {
79                     level2n.append(node.left)
80                     level2n.append(node.right)
81                 }
82             }
83             
84             level1 = level1n
85             level2 = level2n
86             level1n = []
87             level2n = []
88         }
89         
90         return true
91     }
92 }

24ms

 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 flipEquiv(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
16         
17         if root1 == nil && root2 == nil {
18             return true
19         } else if root1 == nil {
20             return false
21         } else if root2 == nil {
22             return false
23         }
24         
25         let _r1 = root1!
26         let _r2 = root2!
27         
28         return _r1.val == _r2.val &&
29         (flipEquiv(_r1.left, _r2.right) || flipEquiv(_r1.left, _r2.left)) &&
30         (flipEquiv(_r1.right, _r2.left) || flipEquiv(_r1.right, _r2.right))
31     }
32 }

40ms

 1 class Solution {
 2     static let size = 100
 3     var m1: Array<Array<Int>> = [[Int]].init(repeating: [Int].init(repeating: -1, count: size), count: size)
 4     var m2: Array<Array<Int>> = [[Int]].init(repeating: [Int].init(repeating: -1, count: size), count: size)
 5     
 6     func flipEquiv(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
 7         var s1: Int = 0
 8         var s2: Int = 0
 9         treeMap(root1, &m1, 0, size: &s1)
10         treeMap(root2, &m2, 0, size: &s2)
11         if s1 != s2 { return false }
12         return checkEquiv(m1, m2)
13     }
14     
15     func checkEquiv(_ r1: [[Int]], _ r2: [[Int]]) -> Bool  {
16         for i in 0..<Solution.size {
17             for j in 0..<Solution.size {
18                 if r1[i][j] != r2[i][j] {
19                     return false
20                 }
21             }
22         }
23         return true
24     }
25     
26     func treeMap(_ node: TreeNode?,
27                  _ arr: inout [[Int]],
28                  _ lvl: Int,
29                  size: inout Int) {
30         if let n = node {
31             size += 1
32             if let r = n.right {
33                 arr[n.val][r.val] = lvl
34                 treeMap(r, &arr, lvl+1, size: &size)
35             }
36             if let l = n.left {
37                 arr[n.val][l.val] = lvl
38                 treeMap(l, &arr, lvl+1, size: &size)
39             }
40         }
41     }
42 }