[数据结构与算法]94. 二叉树的中序遍历

迭代法

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res =[]
        stack = []
        cur = root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res

递归

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