• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[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],

    3
   / \
  9  20
    /  \
   15   7

 

return its bottom-up level order traversal as:

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

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

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

    3
   / \
  9  20
    /  \
   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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap