94. Binary Tree Inorder Traversa

94. Binary Tree Inorder Traversal

题目:
https://leetcode.com/problems/binary-tree-inorder-traversal/

难度:

Medium

递归

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.lst = []
        self.DFS(root)
        return self.lst

    
    def DFS(self,root):
        if root == None:
            return
        if root.left:
            self.DFS(root.left)
        self.lst.append(root.val)
        if root.right:
            self.DFS(root.right)
                

非递归用stack，我听谁讲过 😓

// to be done

via wikipedia

递归：

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

非递归,跟之前那个iterator有得一拼，其实好几个题都是在玩这个花样？

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right