145. 二叉树的后序遍历 - 中等

145. 二叉树的后序遍历

二叉树遍历

二叉树的后序遍历 左 右 根

当根节点的左右子树均为空的时候 add root.val

递归解法

• 时间复杂度
  O(n) n 是二叉树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度
  O(n) 为递归过程中栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

func postorderTraversal(_ root: TreeNode?) -> [Int] {
        var list: [Int] = []
        postorder(root, &list)
        return list
    }

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

真迭代解法

• 时间复杂度
  O(n) n 是二叉树的节点数。每一个节点恰好被遍历一次。
• 空间复杂度
  O(n) 为迭代过程中显式栈的开销，平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

func postorderTraversal1(_ root: TreeNode?) -> [Int] {
        var list: [Int] = []
        var root = root
        var stackTree: [TreeNode] = []
        // 用来记录回退的根节点 在回退的时候 要判断这个是不是刚刚回退的节点 如果不加判断会死循环
        var lastTree: TreeNode?
        while root != nil || !stackTree.isEmpty {
            while root != nil {
                stackTree.append(root!)
                root = root?.left
            }
            root = stackTree.popLast()

            // root.right == nil 时做下列操作很容易理解
            if root?.right == nil || root?.right === lastTree {
                list.append(root!.val)
                // 这个时候要回退了，所以先记录当前的这个节点
                lastTree = root
                // 要把 root 置 nil 进行回退， 否则又是死循环
                root = nil
            } else {
                stackTree.append(root!)
                root = root?.right
            }
        }

        return list
    }

假后序解法

• 时间复杂度
  O(n): O(2n) 因为 2 为常数级，所以是 O(n)。 一个 n 是所有节点的遍历，另一个是最后的反转
• 空间复杂度
  O(n): O(2n) 因为 2 为常数级，所以是 O(n)。一个 n 是迭代栈的开销，一个是最后反转的开销

func postorderTraversal2(_ root: TreeNode?) -> [Int] {
        var root = root
        var list: [Int] = []
        var stackTree: [TreeNode] = []
        // 后序遍历的顺序是  左右根
        // 反转后是 根右左，和前序遍历的 根左右 很像
        // 所以来用前序遍历的变形写法，然后把得的数据反转就行了
        while root != nil || !stackTree.isEmpty {
            while root != nil {
                list.append(root!.val)
                stackTree.append(root!)
                root = root?.right
            }
            root = stackTree.popLast()
            root = root?.left
        }

        return list.reversed()
    }