题目描述

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

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

解答方法

方法一：递归

代码

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

时间复杂度

T(n)=2T(n/2)+1

空间复杂度

最坏情况下需要空间O(n),平均情况为O(logn)

提交结果

Runtime: 36 ms, faster than 71.47% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.7 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.

方法二：基于栈的遍历

代码

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

时间复杂度

O(n)

空间复杂度

O(n)

提交结果

Runtime: 40 ms, faster than 37.12% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.9 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.

方法三：莫里斯遍历

代码

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        current = root
        while current is not None:
            if current.left is None:
                res.append(current.val)
                current = current.right
            else:
                pre = current.left
                while pre.right is not None:
                    pre = pre.right
                pre.right,current.left, current = current, None,  current.left
                
        return res

时间复杂度

O （n ）。想要证明时间复杂度是O （n ），最大的问题是找到每个节点的前驱节点的时间复杂度。乍一想，找到每个节点的前驱节点的时间复杂度应该是O （nlogn ），因为找到一个节点的前驱节点和树的高度有关。
但事实上，找到所有节点的前驱节点只需要O （n ）时间。一棵ñ个节点的二叉树只有ñ- 1条边，每条边只可能使用2次，一次是定位节点，一次是找前驱节点。
故复杂度为O （n ）。

空间复杂度

O （n ）。使用了长度为ñ的数组。

提交结果

Runtime: 40 ms, faster than 37.12% of Python3 online submissions for Binary Tree Inorder Traversal.
Memory Usage: 13.9 MB, less than 6.56% of Python3 online submissions for Binary Tree Inorder Traversal.