[Swift]LeetCode1110. 删点成林 | Delete Nodes And Return Forest

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

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

示例：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

提示：

树中的节点数最大为 1000。
每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
to_delete.length <= 1000
to_delete 包含一些从 1 到 1000、各不相同的值。

56ms

 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     var ans = [TreeNode?]()
16     func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
17         var root = root
18         if root != nil {
19             if !to_delete.contains(root!.val) { ans.append(root) }
20             traverseDelNodes(&root, Set<Int>(to_delete))
21         }
22         return ans
23     }
24 
25     func traverseDelNodes(_ root: inout TreeNode?, _ to_delete: Set<Int>) {
26         if root == nil { return }
27         if to_delete.contains(root!.val) {
28             if root!.left != nil {
29                 if !to_delete.contains(root!.left!.val) { ans.append(root!.left) }
30                 traverseDelNodes(&root!.left, to_delete)
31             }
32 
33             if root!.right != nil {
34                 if !to_delete.contains(root!.right!.val) { ans.append(root!.right) }
35                 traverseDelNodes(&root!.right, to_delete)
36             }
37             root = nil
38             return
39         }
40         if root!.left != nil { traverseDelNodes(&root!.left, to_delete) }
41         if root!.right != nil { traverseDelNodes(&root!.right, to_delete) }
42     }
43 }

60ms

 1 class Solution {
 2   var rootNodes = [TreeNode]()
 3   var toDeleteSet: Set<Int>!
 4   
 5   func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
 6     toDeleteSet = Set<Int>(to_delete)
 7     helper(parent: nil, isRight: true, needToAdd: true, node: root)
 8     return rootNodes
 9   }
10   
11   func helper(parent: TreeNode?, isRight: Bool, needToAdd: Bool, node: TreeNode?) {
12     guard let n = node else { return }
13     if toDeleteSet.contains(n.val) {
14       if isRight {
15         parent?.right = nil
16       } else {
17         parent?.left = nil
18       }
19       helper(parent: n, isRight: true, needToAdd: true, node: n.right)
20       helper(parent: n, isRight: false, needToAdd: true, node: n.left)
21     } else {
22       if needToAdd {
23         rootNodes.append(n)
24       }
25       helper(parent: n, isRight: true, needToAdd: false, node: n.right)
26       helper(parent: n, isRight: false, needToAdd: false, node: n.left)
27     }
28   }
29 }

64ms

 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     var ans = [TreeNode?]()
16     func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
17         var root = root
18         if root != nil {
19             if !to_delete.contains(root!.val) { ans.append(root) }
20             traverseDelNodes(&root, Set<Int>(to_delete))
21         }
22         return ans
23     }
24 
25     func traverseDelNodes(_ root: inout TreeNode?, _ to_delete: Set<Int>) {
26         if root == nil { return }
27         if to_delete.contains(root!.val) {
28             var left = root!.left
29             var right = root!.right
30             root = nil
31             if left != nil {
32                 if !to_delete.contains(left!.val) { ans.append(left) }
33                 traverseDelNodes(&left, to_delete)
34             }
35 
36             if right != nil {
37                 if !to_delete.contains(right!.val) { ans.append(right) }
38                 traverseDelNodes(&right, to_delete)
39             }
40             return
41         }
42         if root!.left != nil { traverseDelNodes(&root!.left, to_delete) }
43         if root!.right != nil { traverseDelNodes(&root!.right, to_delete) }
44     }
45 }

Runtime: 72 ms

Memory Usage: 22.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     var ans:[TreeNode?] = [TreeNode?]()
16     var ds:Set<Int> = Set<Int>()
17     
18     func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
19         for x in to_delete
20         {
21             ds.insert(x)
22         }
23         dfs(root,1)
24         return ans
25     }
26     
27     func dfs(_ v: TreeNode?, _ top:Int) -> TreeNode?
28     {
29         if v == nil
30         {
31             return v
32         }
33         if ds.contains(v!.val)
34         {
35             dfs(v!.left,1)
36             dfs(v!.right,1)
37             return nil
38         }
39         if top != 0
40         {
41             ans.append(v)
42         }
43         v?.left = dfs(v!.left,0)
44         v?.right = dfs(v!.right,0)
45         return v
46     }
47 }

104ms

 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 delete(_ root: TreeNode, _ parent: TreeNode?, _ toDel: inout [Int], _ result: inout [TreeNode?]) {
16         var nextParent: TreeNode? = root
17         if let toDelIdx = toDel.firstIndex(of: root.val) {
18             toDel.remove(at: toDelIdx)
19             
20             if let parentSteady = parent {
21                 if parentSteady.left === root {
22                     parentSteady.left = nil
23                 }
24                 if parentSteady.right === root {
25                     parentSteady.right = nil
26                 }
27             }
28             nextParent = nil
29         } else if parent == nil {
30             result.append(root)
31         }
32         
33         if let nodeLeft = root.left {
34             delete(nodeLeft, nextParent, &toDel, &result)
35         }
36 
37         if let nodeRight = root.right {
38             delete(nodeRight, nextParent, &toDel, &result)
39         }
40     }
41     
42     func delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
43         var result: [TreeNode?] = []      
44         if let rootSteady = root {
45             var toDel = to_delete
46             delete(rootSteady, nil, &toDel, &result)
47         }
48         if result.isEmpty {
49             result = [ nil ]
50         }
51         return result
52     }
53 }

176ms

 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 delNodes(_ root: TreeNode?, _ to_delete: [Int]) -> [TreeNode?] {
16         //traverse tree, when find node, add left/right child to the results.
17         var results = [TreeNode?]()
18         guard let root = root else {return results}
19        
20         var trees = [TreeNode]() 
21         trees.append(root)
22         while trees.count > 0 {
23             var tree = trees.removeFirst()
24             if to_delete.contains(tree.val) {
25                 //this is not valid tree, no need to add to list, leave it out
26                 if let left = tree.left {
27                     trees.append(left)
28                 }
29                 if let right = tree.right {
30                     trees.append(right)
31                 }
32             } else {
33                 results.append(tree)
34                 dfs(tree, to_delete, &trees)
35             }
36         }
37         
38       
39         return results
40     }
41     
42     func dfs(_ node: TreeNode?, _ toDelete: [Int], _ trees: inout [TreeNode]) {
43         guard let node = node else {return}
44         
45         if let left = node.left {
46             if toDelete.contains(left.val) {
47                 trees.append(left)
48                 node.left = nil
49             } else {
50                 dfs(node.left, toDelete, &trees)
51             }
52         }
53         
54          if let right = node.right {
55             if toDelete.contains(right.val) {
56                 trees.append(right)
57                 node.right = nil
58             } else {
59                 dfs(node.right, toDelete, &trees)
60             }
61         }
62        
63     }
64 }