【MEDIUM】Binary Tree Zigzag Level Order Traversal

发布于: 2018-12-08 01:13
阅读: 71
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

分析过程

  • 输入:二叉树
  • 输出:之字形遍历结果
  • 思路:利用队列进行广度优先搜索,分层记录。偶数层利用栈反序一次。

解决方法

class Solution {
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }
        // 分层结果
        var result = [[TreeNode]]()
        // 临时队列
        var queue = [TreeNode]()
        // 记录层数用来之字形反序
        var level = -1
        
        // 广度搜索,根节点弹出队列,把左右子节点入队列,就能拿到该层的所有节点了
        queue.append(root)
        
        while queue.count != 0 {

            result.append([TreeNode]())
            level += 1
            
            for _ in 0..<queue.count {
                let first = queue.removeFirst()
                
                // zigzag
                if level % 2 == 0 {
                    result[level].append(first)
                } else {
                    // 这里需要反向,偷懒用了insert,最好用栈
                    result[level].insert(first, at: 0)
                }
                
                
                if first.left != nil {
                    queue.append(first.left!)
                }
                
                if first.right != nil {
                    queue.append(first.right!)
                }
            }
        }
        
        return result.map { $0.map { $0.val } }
    }
}

Thanks for reading.

All the best wishes for you! 💕