初级算法-树-二叉树的层序遍历

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

补充内容

摘一个示例做个说明.
示例 1：
二叉树：[3,9,20,null,null,15,7],
 3
   / \
  9  20
    /  \
   15   7
返回其层序遍历结果：

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

条件分析:

1. 二叉树层序遍历
2. 返回数组

解决思路1:

1. 根据分析1,需要分层获取,从root开始,然后按层访问
2. 采用数组进行存储

先判断树是否为空,空则返回.否则创建数组,数组存放二叉树一条数据元素.然后定义返回结果及层序临时数组.然后进行迭代判断数据数组是否为空,不为空则创建临时数组.进行循环判断数据数组内容.采用临时数组进行存储.然后判断是否存在左右节点.然后返回数组添加临时数组内容.数据数组删所有数据后赋值为层序临时数组,然后删除内容,直至循环结束.

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let tree = root else { return [] }
    var array: [TreeNode] = [tree]
    var result: [[Int]] = []
    //临时存储数组
    var nextLevelArray: [TreeNode] = []
    while array.count != 0 {
        var temp: [Int] = []
        for node in array {
            temp.append(node.val)
            if let left = node.left {
                nextLevelArray.append(left)
            }
            if let right = node.right {
                nextLevelArray.append(right)
            }
        }
        result.append(temp)
        array.removeAll()
        array = nextLevelArray
        nextLevelArray.removeAll()
    }
    return result
}

二叉树的层序遍历提交结果.jpg

测试用例:

let root = TreeNode()
root.val = 1
let firLeft = TreeNode()
firLeft.val = 2
let firRight = TreeNode()
firRight.val = 2
let secFirLeftLeft = TreeNode()
secFirLeftLeft.val = 3
let secFirLeftRight = TreeNode()
secFirLeftRight.val = 4
let secFirRightLeft = TreeNode()
secFirRightLeft.val = 4
let secFirRightRight = TreeNode()
secFirRightRight.val = 3
root.left = firLeft
root.right = firRight
firLeft.left = secFirLeftLeft
firLeft.right = secFirLeftRight
firRight.left = secFirRightLeft
firRight.right = secFirRightRight

考察要点:

• 树
• 广度搜索优先
• 二叉树