【MEDIUM】Binary Tree Zigzag Level Order Traversal

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

问题

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 Node {
    var val: Int
    var left: Node?
    var right: Node?
    
    init(val: Int) {
        self.val = val
    }
}

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

        result.append([Node]())
        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
}


//    1
//  2   3
// 4 5 6 7

let root = Node.init(val: 1)
root.left = Node.init(val: 2)
root.left?.left = Node.init(val: 4)
root.left?.right = Node.init(val: 5)
root.right = Node.init(val: 3)
root.right?.left = Node.init(val: 6)
root.right?.right = Node.init(val: 7)

print(levelOrderZigzag(root).map { $0.map { $0.val } })

Thanks for reading.

All the best wishes for you! 💕