Swift 二叉树的层次遍历 - LeetCode

LeetCode

题目： 二叉树的层次遍历

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

例如: 给定二叉树:[3,9,20,null,null,15,7],

代码语言：javascript复制

    3
   / 
  9  20
    /  
   15   7

返回其层次遍历结果：

代码语言：javascript复制

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

二叉树的层次遍历其实就是图的广度优先遍历BFS(Breadth-First-Search)

二叉树的层次遍历代码：

代码语言：javascript复制

    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
     }

使用该题例子返回结果：

代码语言：javascript复制

[3, 9 , 20, 15, 7]

要使得答案符合题意，需要每一层单独分组，修改代码如下

代码语言：javascript复制

/**
 * 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: 前、中、后序遍历中的前，中，后说的是根节点的位置，左节点一定在右节点之前遍历

代码语言：javascript复制

    //前序遍历  根节点 -> 左节点 -> 右节点
    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我哦。

swift

0 人点赞