LeetCode 102 二叉树的层次遍历 [Swift]
2019-11-15
题目
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
示例:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[ [3], [9,20], [15,7] ]
思路
本题采用递归对树的每一层节点进行遍历，在逐层遍历的过程中，将这一层的节点值记录并加入数组，代码实现如下:
/**
* 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 {
var ret : [[Int]] = [[Int]]()
func levelOrder(_ root: TreeNode?) -> [[Int]] {
if root == nil {
return [];
}
levelTravel([root!])
return ret;
}
func levelTravel(_ nodes: [TreeNode]) {
if nodes.count == 0 {
return
}
var children = [TreeNode]()
var levelValues = [Int]()
for node in nodes {
levelValues.append(node.val)
if let left = node.left {
children.append(left)
}
if let right = node.right {
children.append(right)
}
}
ret.append(levelValues)
levelTravel(children)
}
}
本题考查的是树的层次遍历（BFS），除了递归的方法，我们还可以利用队列 “先进先出” 的特性对树进行层次遍历。