94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

思路

通过递归很容易实现：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        l = []
 
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            l.append(node.val)
            dfs(node.right)
        dfs(root)
        return l

如果要使用迭代实现的话，需要借助栈完成，简单来说，我们自己维护一个栈，从根节点开始处理左侧结点，在遇到叶子时停止，弹出栈中的值并放入列表中，再处理右边的结点。循环逻辑是判断栈和当前节点是否为空：

最终代码

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stack = []
        node = root
        ret = []
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            ret.append(node.val)
            node = node.right
        return ret

想得太多