Swift 二叉树的层次遍历 - LeetCode
LeetCode
题目： 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树:[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]二叉树的层次遍历其实就是图的广度优先遍历BFS(Breadth-First-Search)
二叉树的层次遍历代码：
func levelOrder(_ root: TreeNode?) -> [Int] {
guard root != nil else { return [] }
var res = [Int]()
var queue = [TreeNode]()
queue.append(root!)
while !queue.isEmpty {
let node = queue.removeFirst()
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
res.append(node.val)
}
return res
}使用该题例子返回结果：
[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 {
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard root != nil else { return [] }
var queue = [TreeNode]()
var res = [[Int]]()
queue.append(root!)
while !queue.isEmpty {
let size = queue.count
var level = [Int]() //存放该层所有数值
for _ in 0..<size {
let node = queue.removeFirst()
level.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
res.append(level)
}
return res
}
}二叉树常用遍历方式：
- tips: 前、中、后序遍历中的前，中，后说的是根节点的位置，左节点一定在右节点之前遍历
//前序遍历 根节点 -> 左节点 -> 右节点
func preOrder(_ root: TreeNode?) -> Void {
guard root != nil else { return }
print("\(root!.val)\t", terminator: "")
preOrder(root!.left)
preOrder(root!.right)
}
//中序遍历 左节点 -> 根节点 -> 右节点
func midOrder(_ root: TreeNode?) -> Void {
guard root != nil else { return }
midOrder(root!.left)
print("\(root!.val)\t", terminator: "")
midOrder(root!.right)
}
//后续遍历 左节点 -> 右节点 -> 根节点
func afterOrder(_ root: TreeNode?) -> Void {
guard root != nil else { return }
afterOrder(root!.left)
afterOrder(root!.right)
print("\(root!.val)\t", terminator: "")
}用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.12.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录