[Swift]LeetCode107. 二叉树的层次遍历 II | Binary Tree Level Order Traversal II ... - Swift 教程-OStack程序员社区-中国程序员成长平台

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

[Swift]LeetCode107. 二叉树的层次遍历 II | Binary Tree Level Order Traversal II ...

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

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

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

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

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

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

12ms

/**
 * 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 levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
        //递归方法
        //当depth递归到上一层的个数，新建一个空层，继续往里面加数字。
        var res:[[Int]] =  [[Int]]()
        if root == nil {return res}
        var intList:[Int] = [Int]()
        levelOrder(root , 0 , &res)
        var temp:[Int] = [Int]()
        let num:Int = res.count-1
        //交换第一位和最后一位
        //交换第二位和倒数第二位......
        for i in 0...num
        {
            temp = res[i]
            res[i] = res[num-i]
            res[num-i] = temp
        }
        return res.reversed()
    }
    func levelOrder(_ root: TreeNode?, _ depth:Int,_ re: inout [[Int]] )
    {
        if root == nil {return}
        if (depth + 1) > re.count 
        {
            re.append([Int]())
        }
        re[depth].append(root!.val)
        levelOrder(root!.left,depth+1,&re)
        levelOrder(root!.right,depth+1,&re)    
    }
}

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 levelOrderBottom (_ root: TreeNode?) -> [[Int]] {
16         var res = [[Int]]()
17         checkValuesOnLevel(&res, node: root, level: 0)
18         return res
19     }
20     
21     func checkValuesOnLevel (_ res: inout [[Int]], node: TreeNode?, level: Int) {
22         guard let node = node else { return }
23         if level >= res.count {
24             res.insert ([], at: 0)
25         }
26         checkValuesOnLevel(&res, node: node.left, level: level + 1)
27         checkValuesOnLevel(&res, node: node.right, level: level + 1)
28         res[res.count - level - 1].append(node.val)
29     }
30 }

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 levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
16             guard let tNode = root else {
17         return []
18     }
19     var result: [[Int]] = []
20     var tempNodes: [TreeNode] = [tNode]
21     while !tempNodes.isEmpty {
22         let count = tempNodes.count
23         var data: [Int] = []
24         for i in 0..<count {
25             let node = tempNodes[i]
26             data.append(node.val)
27             if let lNode = node.left {
28                 tempNodes.append(lNode)
29             }
30             if let rNode = node.right {
31                 tempNodes.append(rNode)
32             }
33         }
34         tempNodes.removeSubrange(Range.init(NSRange(location: 0, length: count))!)
35         result.append(data)
36     }
37     return result.reversed()
38     }
39 }

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 levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
16         if root == nil {
17             return []
18         }
19         
20         var result = [[Int]]()
21         var queue = [TreeNode]()
22         queue.append(root!)
23         while !queue.isEmpty {
24             var count = queue.count
25             var temp = [Int]()
26             while count != 0 {
27                 let node = queue.removeFirst()
28                 temp.append(node.val)
29                 if node.left != nil {
30                     queue.append(node.left!)
31                 }
32                 if node.right != nil {
33                     queue.append(node.right!)
34                 }
35                 count -= 1
36             }
37             result.append(temp)
38         }
39         
40         return result.reversed()
41     }
42 }