094._binary_tree_inorder_traversal.md

###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

preorder/ inorder / postorder都有iterative模式，可以看wikipedia

so:

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        node = root

        while len(stack) > 0 or node != None:
            if node != None:
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                res.append(node.val)
                node = node.right

        return res