题意

给定一个二叉树，返回它的中序 遍历数组；

解题思路

1. 递归：往左子结点深度递归，在其代码下面加入当前结点的值，接着往右子结点进行深度递归；

2. 迭代：利用栈后进先出的特性，一直将左子结点都加入到栈中，直到其不存在时，将当前结点的值加入到结果列表中，接着将当前结点的右结点加入到栈中；

实现

class Solution(object):     def inorderTraversal(self, root):         """         递归实现         :type root: TreeNode         :rtype: List[int]         """         result = []         if not root:             return result                  def helper(node, res):             if not node:                 return             helper(node.left, res)             res.append(node.val)             helper(node.right, res)                  helper(root, result)         return result       def inorderTraversal(self, root):         """         迭代实现         执行用时 : 44 ms, 在Binary Tree Inorder Traversal的Python提交中击败了1.11% 的用户     内存消耗 : 11.9 MB, 在Binary Tree Inorder Traversal的Python提交中击败了0.89% 的用户         :type root: TreeNode         :rtype: List[int]         """         result = []         stack = []         cur = root         while cur or stack:             if cur:                 stack.append(cur)                 cur = cur.left             else:                 cur = stack.pop()                 result.append(cur.val)                 cur = cur.right         return result