[Swift]LeetCode617. 合并二叉树 | Merge Two Binary Trees_app

概述Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree.

Given two binary trees and imagine that when you put one of them to cover the other,some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap,then sum node values up as the new value of the merged node. Otherwise,the NOT null node will be used as the node of new tree.

Example 1:

input: 	Tree 1                     Tree 2                            1                         2                                      / \                       / \                                    3   2                     1   3                               /                           \   \                            5                             4   7                  Output: Merged tree:	     3	    / 	   4   5	  / \   \ 	 5   4   7

Note: The merging process must start from the root nodes of both trees.

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NulL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 	Tree 1                     Tree 2                            1                         2                                      / \                       / \                                    3   2                     1   3                               /                           \   \                            5                             4   7                  输出: 合并后的树:	     3	    / 	   4   5	  / \   \ 	 5   4   7

注意: 合并必须从两个树的根节点开始。

Runtime: 100 ms Memory Usage: 19.8 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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {16         if t1 == nil {return t2}17         if t2 == nil {return t1}18         var t = TreeNode(t1!.val + t2!.val)19         t.left =  mergeTrees(t1!.left,t2!.left)20         t.right = mergeTrees(t1!.right,t2!.right)21         return t22     }23 }

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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {16         switch (t1,t2) {17         case (let t1,nil) where t1 != nil:18             return t1!19         case (nil,let t2) where t2 != nil:20             return t2!21         case (nil,nil):22             return nil23         default:24             guard let tree1 = t1,let tree2 = t2 else { return nil }25             let newTree = TreeNode(tree1.val + tree2.val)26             newTree.left = mergeTrees(tree1.left,tree2.left)27             newTree.right = mergeTrees(tree1.right,tree2.right)28             return newTree29         }30     }31 }

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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {        16         guard let t1 = t1 else {17             return t218         }19         20         guard let t2 = t2 else {21             return t122         }23         24         t1.val += t2.val25         t1.left = mergeTrees(t1.left,t2.left)26         t1.right = mergeTrees(t1.right,t2.right)27         return t128     }        29 }

136ms

 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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {16             if t1 == nil && t2 == nil { return nil }17             var newNode = TreeNode((t1?.val ?? 0) + (t2?.val ?? 0))18 19             if t1?.left == nil || t2?.left == nil {20                 newNode.left = t1?.left ?? t2?.left                    21             } else {22                 newNode.left = mergeTrees(t1?.left,t2?.left)23             }24             25             if t1?.right == nil || t2?.right == nil {26                 newNode.right = t1?.right ?? t2?.right                    27             } else {28                 newNode.right = mergeTrees(t1?.right,t2?.right)29             }30             31             return newNode32     }33 }

160ms

 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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {16     switch (t1,t2) {17     case (nil,_): return t218     case (_,nil): return t119         default:20             var treeNode: TreeNode21             treeNode = TreeNode(t1!.val + t2!.val)22             treeNode.left = mergeTrees(t1!.left,t2!.left)23             treeNode.right = mergeTrees(t1!.right,t2!.right)24             return treeNode25         }26     }27 }

204ms

 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 = nil10  *         self.right = nil11  *     }12  * }13  */14 class Solution {15     var A = TreeNode(0)16     func mergeTrees(_ t1: TreeNode?,_ t2: TreeNode?) -> TreeNode? {17         if t1 == nil && t2 == nil{18             return t119         }else{20             B(t1,t2,A)21         }22         23         return A24     }25     func B(_ t1: TreeNode?,_ t2: TreeNode?,_ t3: TreeNode?)26     {27         if t1?.left != nil && t2?.left != nil28         {29             t3?.left = TreeNode(0)30             B(t1?.left,t2?.left,t3?.left)31         }else if t1?.left == nil && t2?.left != nil{32             t3?.left = TreeNode(0)33             B(nil,t3?.left)34         }else if t1?.left != nil && t2?.left == nil{35             t3?.left = TreeNode(0)36             B(t1?.left,nil,t3?.left)37         }38         39         if t1 != nil && t2 != nil40         {41             let a:Int = t1?.val as! Int42             let b:Int = t2?.val as! Int43             t3?.val = a + b44         }else if t1 == nil && t2 != nil{45             let b:Int = t2?.val as! Int46             t3?.val = b47         }else if t1 != nil && t2 == nil{48             let a:Int = t1?.val as! Int49             t3?.val = a50         }else{51             return52         }53         54         if t1?.right != nil && t2?.right != nil55         {56             t3?.right = TreeNode(0)57             B(t1?.right,t2?.right,t3?.right)58         }else if t1?.right == nil && t2?.right != nil{59             t3?.right = TreeNode(0)60             B(nil,t3?.right)61         }else if t1?.right != nil && t2?.right == nil{62             t3?.right = TreeNode(0)63             B(t1?.right,t3?.right)64         }else{65             return66         }        67     }68 }