题

题号：94

题目：二叉树的中序遍历

难度：简单

链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/

2022/08/23答案

算法思路

  本题在课程中是学过的。

  大致的思路就是利用迭代。首先是前序、中序、后序的遍历的意思，可以直接通过前/中/后这三个字来理解。前就是第一个遍历根节点（根节点->左子树->右子树），中就是第二个遍历根节点（左子树->根节点->右子树），后就是最后再遍历根节点（左子树->右子树->根节点）。

  那样的话，可以通过递归的思想来实现。

  当然因为递归对我来说真的是只可意会不可言传（我真的不是特别的能理解递归）。

代码

class Solution:

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        查看数据
        TreeNode{val: 1, left: None, right: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}}
        """
        if root == None:
            return []
        li_out = []
        li_out = self.inorderTraversal(root.left)

        li_out.append(root.val)

        li_out.extend(self.inorderTraversal(root.right))

        return li_out

结果

思考

  让我自己写递归的话，我肯定是不行的。但进阶版貌似是利用迭代？稍后会再行思考。