LetCode in Swift (617-Merge Two Binary Trees)

文章目录

1. 1. 文档更新说明
2. 2. 前言
3. 3. 617. Merge Two Binary Trees
   1. 3.1. Example1
   2. 3.2. Note
   3. 3.3. Solution

文档更新说明

• 最后更新 2018年03月09日
• 首次更新 2018年03月09日

前言

　　使用Swift语言完成LetCode题目,简单难度

617. Merge Two Binary Trees

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.

Example1

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.

Solution

　　题意是给出两个二叉树,合并成一个.同个位置的节点,合并之后的新节点的值就是两节点只和;如果同个位置缺少了一个节点,则其直接成为新节点;若两个节点都是空的,则合并之后的节点则为空.
　　对于每一个节点来说,都是在重复上诉步骤,所以可以采用递归算法,比较容易实现.

import Foundation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    // 这道题采用递归算法解决.看起来应该是中等难度的题目,不知道为什么标记成简单题.
    func mergeTrees(_ t1: TreeNode?, _ t2: TreeNode?) -> TreeNode? {
        //注意递归的结束条件
        if t1 == nil && t2 == nil {
            return nil
        }
        //创建一个跟踪节点newNode, 记录t1,t2树每一个节点merge之后的节点数值
        //之后newNode的左右树,继续重复merge
        let newNode: TreeNode
        if let v1 = t1?.val, let v2 = t2?.val {
            newNode = TreeNode(v1 + v2)
            newNode.left = mergeTrees(t1?.left, t2?.left)
            newNode.right = mergeTrees(t1?.right, t2?.right)
        }else if let v1 = t1?.val {
            newNode = TreeNode(v1)
            newNode.val = v1
            newNode.left = mergeTrees(t1?.left, nil)
            newNode.right = mergeTrees(t1?.right, nil)
        }else {
            let v2 = t2?.val
            newNode = TreeNode(v2!)
            newNode.left = mergeTrees(nil, t2?.left)
            newNode.right = mergeTrees(nil, t2?.right)
        }
        
        return newNode
    }
}

private func makeT1() -> TreeNode {
    // Tree1
    let t1 = TreeNode(1)
    let n0 = t1
    let n1 = TreeNode(3)
    let n2 = TreeNode(2)
    let n3 = TreeNode(5)
    n0.left = n1
    n0.right = n2
    n1.left = n3
    
    return t1
}

private func makeT2() -> TreeNode {
    let t2 = TreeNode(2)
    let n0 = t2
    let n1 = TreeNode(1)
    let n2 = TreeNode(3)
    let n3 = TreeNode(4)
    let n4 = TreeNode(7)
    n0.left = n1
    n0.right = n2
    n1.right = n3
    n2.right = n4
    return t2
}

let t1 = makeT1()
let t2 = makeT2()
let s = Solution()
let t = s.mergeTrees(t1, t2)
print(t)