题目

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

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶:

递归算法很简单，你可以通过迭代算法完成吗？

题解

方法都是力扣官方题解的，做了Python化地处理并且做了些许调整。

递归

参考https://leetcode-cn.com/problems/two-sum/solution/python-di-gui-die-dai-by-knifezhu/

1
2
3
4
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        f = self.inorderTraversal
        return f(root.left) + [root.val] + f(root.right) if root else []

非递归（堆栈）

参考评论区

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res, st, n = [], [], root
        while n or st:
            while n:
                st.append(n)
                n = n.left
            n = st.pop()
            res.append(n.val)
            n = n.right
        return res

莫里斯遍历

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res, curr = [], root
        while curr is not None: 
            if curr.left is None:
                res.append(curr.val)
                curr = curr.right
            else: 
                pre = curr.left
                while pre.right is not None: pre = pre.right
                pre.right, curr.left, curr,  = curr, None, curr.left
        return res