94. Binary Tree Inorder Traversa

环境：python 3.6，scala 2.11.8

题意

二叉树的中序遍历

分析

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

• 中序遍历：对一颗二叉树及其子树的遍历顺序为，左子树->根节点->右子树；
• 递归法/使用栈；

代码

python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

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

    dfs(root)
    return rs


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

    return dfs(root)


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

    return rs


def inorderTraversalV4(root: TreeNode):
    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.right, 0))
                stack.append((curr, 1))
                stack.append((curr.left, 0))
    return rs

scala

• scala v2.13 中有 LazyList 类型，可视为加强版 List，感兴趣可戳此。用时更少。

/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
import scala.collection.mutable.ListBuffer

object Solution {
  def inorderTraversal(root: TreeNode): List[Int] = {
    val rs = ListBuffer[Int]()
    def dfs(node: TreeNode): Unit = {
      if (node != null) {
        dfs(node.left)
        rs.append(node.value)
        dfs(node.right)
      }
    }
    dfs(root)
    rs.toList
  }
  
  // 慢于第一种，充分发挥 List 特性
  def inorderTraversalV2(root: TreeNode): List[Int] = {
    def dfs(node: TreeNode): List[Int] = 
      if (node == null) Nil
      else dfs(node.left) ::: List(node.value) ::: dfs(node.right)
      
    dfs(root)
  }
  
    def inorderTraversalV3(root: TreeNode): List[Int] = {
    if (root == null) return Nil
    val rs = ListBuffer[Int]()
    val stack = Stack[TreeNode]()
    var curr = root

    while (stack.nonEmpty || curr != null) {
      while (curr != null) { // 循环体，解决左子节节点
        stack.push(curr)
        curr = curr.left
      }
      val node = stack.pop()
      rs.append(node.value)
      curr = node.right   // 解决右子节节点
    }
    rs.toList
  }

  def inorderTraversalV4(root: TreeNode): List[Int] = {
    if (root == null) return Nil
    val rs = ListBuffer[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, 1))
          stack.push((node.left, 0))
        }
      }
    }
    rs.toList
  }
}

最后

欢迎交流及补充。