中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/submissions/

中序遍历的递归实现还是很容易的，自己在函数里面写过help，再递归去调用即可

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        arr = []
        def help(root):
            if not root:
                return 
            help(root.left)
            arr.append(root.val)
            help(root.right)
        help(root)
        return arr

非递归调用的时候，需要自己用一个队列模拟递归操作
先找到最左的节点，不停的push到队列中，然后取出队列末端元素输出，在遍历其右子树即可

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        arr = []
        queue = []
        tmp = root
        while tmp or queue:
            while tmp:
                queue.append(tmp)
                tmp = tmp.left
            last = queue.pop()
            arr.append(last.val)
            tmp = last.right
            
        return arr