六虎

Swift – LeetCode – 二叉树的后序遍历

Swift – LeetCode – 二叉树的后序遍历

作者：

胡哥有话说

在

携手创造，一起成长！这是我参与「日新计划 8 月更文应战」的第6天，点击查看活动概况

标题

给你二叉树的根节点 root，回来其节点值的 后序遍历。

示例 1：

Swift - LeetCode - 二叉树的后序遍历

  • 输入：root = [1,null,2,3]
  • 输出：[3,2,1]

示例 2：

  • 输入：root = []
  • 输出：[]

示例 3：

  • 输入：root = [1]
  • 输出：[1]

办法一：递归

思路及解法

首要咱们需求了解什么是二叉树的后序遍历：依照拜访左子树——右子树——根节点的办法遍历这棵树，而在拜访左子树或许右子树的时分，咱们依照相同的办法遍历，直到遍历完整棵树。因而整个遍历进程天然具有递归的性质，咱们能够直接用递归函数来模仿这一进程。

界说 postorder(root) 表示当时遍历到 root 节点的答案。依照界说，咱们只需递归调用 postorder(root->left) 来遍历 root 节点的左子树，然后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最后将 root 节点的值参加答案即可，递归终止的条件为碰到空节点。

代码

class Solution {
    func preorder(_ root: TreeNode?, _ res: inout [Int]) {
        guard nil != root else {
            return
        }
        preorder(root?.left, &res)
        preorder(root?.right, &res)
        res.append(root!.val)
    }
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        preorder(root, &res)
        return res
    }
}

复杂度剖析

  • 时刻复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点刚好被遍历一次。

  • 空间复杂度：O(n)，为递归进程中栈的开销，均匀状况下为 O(log n)，最坏状况下树出现链状，为 O(n)。

办法二：迭代

思路及解法

咱们也能够用迭代的办法完成办法一的递归函数，两种办法是等价的，区别在于递归的时分隐式地保护了一个栈，而咱们在迭代的时分需求显式地将这个栈模仿出来，其余的完成与细节都相同，详细能够参考下面的代码。

代码

class Solution {
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        if nil == root {
            return res
        }
        var stack: [TreeNode] = []
        var node: TreeNode? = root
        var prev: TreeNode? = nil
        while !stack.isEmpty || nil != node {
            while nil != node {
                stack.append(node!)
                node = node?.left
            }
            node = stack.popLast()
            if nil == node?.right || node?.right == prev {
                res.append(node!.val)
                prev = node
                node = nil
            } else {
                stack.append(node!)
                node = node?.right
            }
        }
        return res
    }
}
extension TreeNode: Equatable {
    public static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {
        return lhs === rhs
    }
}

复杂度剖析

  • 时刻复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点刚好被遍历一次。

  • 空间复杂度：O(n)，为迭代进程中显式栈的开销，均匀状况下为 O(log n)，最坏状况下树出现链状，为 O(n)。

办法三：Morris 遍历

思路及解法

有一种奇妙的办法能够在线性时刻内，只占用常数空间来完成前序遍历。这种办法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中初次提出，因而被称为 Morris 遍历。

  1. 新建暂时节点，令该节点为 root；
  2. 假如当时节点的左子节点为空，则遍历当时节点的右子节点；
  3. 假如当时节点的左子节点不为空，在当时节点的左子树中找到当时节点在中序遍历下的前驱节点；
    • 假如前驱节点的右子节点为空，将前驱节点的右子节点设置为当时节点，当时节点更新为当时节点的左子节点。
    • 假如前驱节点的右子节点为当时节点，将它的右子节点从头设为空。倒序输出从当时节点的左子节点到该前驱节点这条途径上的所有节点。当时节点更新为当时节点的右子节点。
  4. 重复步骤 2 和步骤 3，直到遍历结束。

这样咱们使用 Morris 遍历的办法，后序遍历该二叉搜索树，即可完成线性时刻与常数空间的遍历。

代码

class Solution {
    func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var res: [Int] = []
        if nil == root {
            return res
        }
        var p1: TreeNode? = root
        var p2: TreeNode? = nil
        while (nil != p1) {
            p2 = p1?.left
            if (nil != p2) {
                while (nil != p2?.right && p2?.right != p1) {
                    p2 = p2?.right
                }
                if (nil == p2?.right) {
                    p2?.right = p1
                    p1 = p1?.left
                    continue
                } else {
                    p2?.right = nil
                    addPath(&res, &p1!.left)
                }
            }
            p1 = p1?.right
        }
        var tempNode: TreeNode? = root
        addPath(&res, &tempNode)
        return res
    }
    func addPath(_ res: inout [Int], _ node: inout TreeNode?) {
        var count: Int = 0
        while (nil != node) {
            count += 1
            res.append(node!.val)
            node = node?.right
        }
        var leftCount = res.count - count
        var rightCount = res.count - 1
        while (leftCount < rightCount) {
            let temp: Int = res[leftCount]
            res[leftCount] = res[rightCount]
            res[rightCount] = temp
            leftCount += 1
            rightCount -= 1
        }
    }
}
extension TreeNode: Equatable {
    public static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {
        return lhs === rhs
    }
}

复杂度剖析

  • 时刻复杂度：O(n)，其中 n 是二叉树的节点数。没有左子树的节点只被拜访一次，有左子树的节点被拜访两次。

  • 空间复杂度：O(1)。只操作现已存在的指针（树的闲暇指针），因而只需求常数的额定空间。

更多文章