LeetCode探索-树的遍历- 94二叉树的中序遍历

Leetcode二叉树探索专题链接：
二叉树
树的遍历中二叉树的中序遍历LeetCode链接:
94. 二叉树的中序遍历

中序遍历的介绍

二叉树的中序遍历顺序为: 左子树 --> 根节点 --> 右子树
比如，给定一棵这样的二叉树：

中序遍历： C -> B -> D -> E -> A -> G -> F

回归题目，题目给了一个二叉树，让我们输出该二叉树中序遍历的节点并以一个列表的方式返回。

题解

解法1

利用递归求解:

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def dfs(root: TreeNode):
            nonlocal res
            if not root:
                return None
            dfs(root.left)
            res.append(root.val) #  相比其他顺序遍历只要改变该行代码的位置即可
            dfs(root.right)
        dfs(root)
        return res

解法2

迭代求解：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left #  添加到最深的左子树
            cur = stack.pop()
            res.append(cur.val)
            root = cur.right #  转向右子树
        return res