94 二叉树的中序遍历

标签: 中序遍历, 二叉树, 栈, 遍历

题目

题目链接：94. 二叉树的中序遍历

思路

1. 中序遍历：左 - 根 - 右

2. 栈的实现方式：先用指针找到每颗子树的最左下角，然后进行进出栈操作

代码

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