145. Binary Tree Postorder Trave

环境：python 3.6，scala 2.11.8

题意

二叉树的后序遍历

分析

基础题型。

• 后序遍历：对一颗二叉树及其子树的遍历顺序为，左子树->右子树->根节点；

• 递归法/使用栈；

• 写法可对比参考中序遍历、先序遍历，尤其是先序 V3 & V5、中序 V3、后序 V4 的遍历思路；

代码

python

def postorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    rs = []

    def dfs(node):
        if node:
            dfs(node.left)
            dfs(node.right)
            rs.append(node.val)
    dfs(root)
    return rs


def postorderTraversalV2(root):
    def dfs(node):
        if not node: return []
        return dfs(node.left) + dfs(node.right) + [node.val]

    return dfs(root)


def postorderTraversalV3(root):
    if not root: return []
    rs = []
    stack = [(root, 0)]

    while stack:
        curr, visited = stack.pop()
        if curr:
            if visited:
                rs.append(curr.val)
            else:
                stack.append((curr, 1))
                stack.append((curr.right, 0))
                stack.append((curr.left, 0))
    return rs


def postorderTraversalV4(root):
    if not root: return []
    rs = []
    stack = [root]

    while stack:
        curr = stack.pop()
        if curr:
            rs.append(curr.val)
            stack.append(curr.left)
            stack.append(curr.right)

    return rs[::-1]

scala

import scala.collection.mutable.{ListBuffer, Stack}

object LC145 {
  def postorderTraversal(root: TreeNode): List[Int] = {
    val rs = ListBuffer.empty[Int]
    def dfs(node: TreeNode): Unit = {
      if (node != null) {
        dfs(node.left)
        dfs(node.right)
        rs.append(node.value)
      }
    }

    dfs(root)
    rs.toList
  }

  def postorderTraversalV2(root: TreeNode): List[Int] = {
    if (root == null) List.empty[Int]
    else postorderTraversalV2(root.left) ::: postorderTraversalV2(root.right) ::: List(root.value)
  }

  def postorderTraversalV22(root: TreeNode): List[Int] = {
    root match {
      case node: TreeNode => postorderTraversalV22(node.left) ::: postorderTraversalV22(node.right) ::: List(root.value)
      case _ => List.empty[Int]
    }
  }

  def postorderTraversalV3(root: TreeNode): List[Int] = {
    if (root == null) return List.empty[Int]
    val rs = ListBuffer.empty[Int]
    val stack = Stack[(TreeNode, Int)]((root, 0))

    while (stack.nonEmpty) {
      val (curr, visited) = stack.pop()
      if (curr != null) {
        if (visited == 1) {
          rs.append(curr.value)
        } else {
          stack.push((curr, 1))
          stack.push((curr.right, 0))
          stack.push((curr.left, 0))
        }
      }
    }
    rs.toList
  }

  def postorderTraversalV4(root: TreeNode): List[Int] = {
    if (root == null) return List.empty[Int]
    val rs = ListBuffer.empty[Int]
    val stack = Stack[TreeNode](root)
    
    while (stack.nonEmpty) {
      val curr = stack.pop()
      if (curr != null) {
        rs.append(curr.value)
        stack.push(curr.left)
        stack.push(curr.right)
      }
    }
    rs.toList
  }
}

最后

欢迎交流及补充。