144. Binary Tree Preorder Traver

环境：python 3.6，scala 2.11.8

题意

二叉树的先序遍历

分析

基础题型，不作过多文字叙述。

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

• 递归法/使用栈；

• 写法可对比参考中序遍历；

代码

python

def preorderTraversal(root):
  """
  :type root: TreeNode
  :rtype: List[int]
  """
  rs = []
  def dfs(node):
    if not node: return 
    rs.append(node.val)
    dfs(node.left)
    dfs(node.right)
  
  dfs(root)
  return rs

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

def preorderTraversalV3(root):
  if not root: return []
  rs = []
  stack = []
  curr = root
  
  while stack or curr:
    while curr:
      stack.append(curr)
      rs.append(curr.val)
      curr = curr.left
    node = stack.pop()
    curr = node.right
  
  return rs

def preorderTraversalV4(root):
  if not root: return []
  rs = []
  stack = [(root, 0)]
  
  while stack:
    node, visited = stack.pop()
    if node:
      if visited:
        rs.append(node.val)
      else:
        stack.append((node.right, 0))
        stack.append((node.left, 0))
        stack.append((node, 1))
  return rs

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

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

scala

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

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

    dfs(root)
  }

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

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

    var curr = root
    while (stack.nonEmpty || curr != null) {
      while (curr != null) {
        stack.push(curr)
        rs.append(curr.value)
        curr = curr.left
      }
      val node = stack.pop()
      curr = node.right
    }
    rs.toList
  }

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

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

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

    while (stack.nonEmpty) {
      val node = stack.pop()
      if (node != null) {
        rs.append(node.value)
        stack.push(node.right)
        stack.push(node.left)
      }
    }
    rs.toList
  }
}

最后

欢迎交流及补充。