二叉树的遍历

• 前序：根节点->左子树->右子树
• 中序：左子树->根节点->右子树
• 后序：左子树->右子树->根节点
• 层序：每一层从左到右输出

备注：前中后是以根节点的位置来说的。

实例

1. 根据前序、中序遍历，输出后序遍历

class BackOrder {
    var res: [Int] = []
    var pre: [Int] = []
    var inorder: [Int] = []

    /// 根据前序、中序遍历输出二叉树的后序遍历
    func buildBackOrder(pre: [Int], inorder: [Int]) -> [Int] {
        self.pre = pre
        self.inorder = inorder
        getNode(root: 0, start: 0, end: inorder.count - 1)
        return res
    }

    /// - Parameter root: 前序遍历根结点位置
    /// - Parameter start: 中序遍历子树起始位置
    /// - Parameter end: 中序遍历子树结束位置
    func getNode(root: Int, start: Int, end: Int) {
        guard start <= end else { return }

        var left = start
        // 定位跟在中序遍历中的位置
        while left <= end && inorder[left] != pre[root]  {
            left += 1
        }

        // 递归处理左子树
        getNode(root: root + 1, start: start, end: left - 1)
        // 递归处理右子树
        // 需要找到前序遍历中右子树的起始位置，left - right 表示左子树的数量， + 1 为根结点
        getNode(root: root + left - start + 1, start: left + 1, end: end)

        res.append(pre[root])
    }
}

参考

程序基本功之遍历二叉树