二叉树遍历方式

实现二叉树结点

class BinaryTreeNode {
    
    let val: Int
    var left: BinaryTreeNode?
    var right: BinaryTreeNode?
    
    public init(_ val: Int, left: BinaryTreeNode? = nil, right: BinaryTreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

构造二叉树

let treeNode5 = BinaryTreeNode(5)
let treeNode4 = BinaryTreeNode(4)
let treeNode3 = BinaryTreeNode(3)
let treeNode2 = BinaryTreeNode(2,left: treeNode5)
let treeNode1 = BinaryTreeNode(1,left: treeNode3,right: treeNode4)
let rootNode = BinaryTreeNode(0,left: treeNode1,right: treeNode2)

image.png

前序遍历

给定一个节点，先遍历该节点，然后遍历左子树，然后右子树

func preorder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
        guard let root = root else {
            return
        }
        list.append(root.val)
        preorder(root.left, &list)
        preorder(root.right, &list)
        
    }

前序遍历.png

中序遍历

给定一个节点，先遍历左子树，再遍历当前结点，然后右子树

func inorder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
        guard let root = root else {
            return
        }
        inorder(root.left, &list)
        list.append(root.val)
        inorder(root.right, &list)
        
    }

中序遍历.png

后序遍历

给定一个节点，先遍历左子树，再遍历右子树，然后当前结点

 func postOrder(_ root: BinaryTreeNode?, _ list: inout [Int]) {
        guard let root = root else {
            return
        }
        postOrder(root.left, &list)
        postOrder(root.right, &list)
        list.append(root.val)
    }

后序遍历.png

层序遍历

顾名思义，一层一层的遍历，借助队列的属性实现，
1.将根节点入队
2.依次将队列的元素出队，判断是否有左右节点，将左右节点入队，并且将当前出队的结点值加入数组中
3.继续下一次的入队，左右节点入队，加入值到数组中

    func levelorder(_ root: BinaryTreeNode?, _ list: inout [Int], _ queue: inout Queue<Any>) {
        guard let root = root else {
            return
        }
        //root节点入队
        queue.enQueue(item: root)
        
        while !queue.empty() {
            var perLevelVal = [Int]()//每层节点的值
            for _ in 0..<queue.count() {
                let top = queue.deQueue() as! BinaryTreeNode //将当前节点出队
                if let left = top.left {
                    queue.enQueue(item: left) //left节点入队
                }
                if let right = top.right {
                    queue.enQueue(item: right) //right节点入队
                }
                perLevelVal.append(top.val) //当前节点的值加入数组
            }
            list.append(contentsOf: perLevelVal)
        }
    }

更详细的内容看这里
代码中Queue的定义看这里

leetcode原题

107. 二叉树的层序遍历 II

还是按照队列的特性遍历，注意要把数据插入到最前面，因为题目要求的是倒序

func levelOrderBottom(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }
        var queue = [TreeNode?]()
        var res = [[Int]]()
        queue.append(root)
        
        while !queue.isEmpty {
            let count = queue.count
            var perLevelList = [Int]()
            for _ in 0..<count {
                guard let node = queue.removeFirst() else {
                    continue
                }
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
                perLevelList.append(node.val)
            }
            res.insert(perLevelList, at: 0)
        }
        return res
    }

116. 填充每个节点的下一个右侧节点指针

进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
因此首先想到的是用递归的方式，

image.png
解题思路：
某个节点比如这里从1开始看，1的next是nil，1的left2，right3
left2的next计算公式为：
left2.next=right3。
而2的right5的next计算公式为：
right5.next=left2.next.left
概括一下就是：
给定一个节点A，A的next=节点B，A的左子节点的next等于A的右子节点。而A的右子节点的next等于节点B的左子节点，依次递归每一个节点，直到节点为空即可（可以看出每次节点的关系）

/**
 * Definition for a Node.
 * public class Node {
 *     public var val: Int
 *     public var left: Node?
 *     public var right: Node?
 *     public var next: Node?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *         self.next = nil
 *     }
 * }
 */

class Solution {
     func connect(_ root: Node?) -> Node? {
        
        guard let root = root else {
            return nil
        }
        
        root.left?.next = root.right
        
        if let next = root.next {
            root.right?.next = next.left
        }
        
        connect(root.left)
        connect(root.right)
        return root
    }
}

用层序遍历也可以实现，但是空间复杂度就不会是常量级

117. 填充每个节点的下一个右侧节点指针 II

116题的二叉树是完美二叉树，即每个节点都有左右节点。
但是本题给的条件是二叉树，要注意考虑到多种情况，
比如下面的

image.png

所以再用普通的递归方式不适用，通过依次查找next的方式进行链接

      @discardableResult
    func connect(_ root: Node?) -> Node? {
        
        guard let root = root else {
            return nil
        }
        
        if root.left != nil {
            if root.right != nil {
                //有右节点直接赋值
                root.left?.next = root.right
            } else {
                //没有右节点，查找next节点
                root.left?.next = findNextNode(root:root.next)
            }
        }
        
        if root.right != nil {
            //赋值右节点的值
            root.right?.next = findNextNode(root: root.next)
        }
        
        connect(root.right)
        connect(root.left)
        return root
    }
    
    //通过每层节点的链表依次查找，next节点右left则返回，没有返回right，都没有继续查找下一个next，直到查找完成
    @discardableResult
    private func findNextNode(root: Node?) -> Node? {
        guard let root = root else {
            return nil
        }
        if let left = root.left {
            return left
        }
        if let right = root.right {
            return right
        }
        if let next = root.next {
            return findNextNode(root: next)
        }
        return nil
    }

应该注意的是，这里为什么要先遍历右节点，
借用力扣上的回答，就是先保证右侧节点已经链接成功，

image.png
image.png