35. 二叉树中序遍历

RT

Scala打卡

  // Time: O(n). Space: O(n)
  def inorderTraversalRecursive[T](tree: TreeNode[T]): Seq[T] = {
    if (tree == null) Nil
    else (inorderTraversalRecursive(tree.left) :+ tree.value) ++ inorderTraversalRecursive(tree.right)
  }

  // Time: O(n). Space: O(n)
  def inorderTraversalIterative[T](tree: TreeNode[T]): Seq[T] = {
    val stack = mutable.Stack[TreeNode[T]]()
    var results = Vector[T]()
    var root = tree
    while (root != null || stack.nonEmpty) {
      while (root != null) {
        stack.push(root)
        root = root.left
      }
      root = stack.pop()
      results :+= root.value
      root = root.right
    }
    results
  }

@yangbajing

牛逼:+1: ,加油把所有题目都打卡了。

有些Java版和Scala版写出来没啥区别的就没帖上来了。