94. 二叉树的中序遍历

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

输入:root = [1,2]
输出:[2,1]

示例 5:

输入:root = [1,null,2]
输出:[1,2]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一解

使用递归:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        def dfs(root):
            if not root: return None
            dfs(root.left)
            self.res.append(root.val)
            dfs(root.right)
        dfs(root)
        return self.res
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

二解

使用栈模拟递归,重复下列过程:

  • 向栈中依次加入:根节点 → 左子节点 → 左子节点
  • 出栈,并入栈“出栈节点”的“右子节点“
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack, res = [], []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            res.append(root.val)
            root = root.right
        return res
  • 时间复杂度 O(n):n 为二叉树节点数量,二叉树每个节点都会被访问一次
  • 空间复杂度 O(n):取决于栈深度,在树是一条链时达到最大

三解

Morris 遍历,此方法是树的遍历最优解!建议学会!

当前节点 cur ,一开始 cur 来到树头,循环下面过程,直到 cur = null

  1. cur 无左树, cur = cur.right
  2. cur 有左树,找到左树的最右节点 most right
    1. most right 的右指针指向 null ,most right.right = cur, cur = cur.left
    2. most right 的右指针指向 cur ,most right.right = null, cur = cur.right
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        while root:
            if root.left:
                predecessor = root.left
                while predecessor.right != None and predecessor.right != root:
                    predecessor = predecessor.right
                if not predecessor.right:
                    predecessor.right = root
                    root = root.left
                else:
                    res.append(root.val)
                    predecessor.right = None
                    root = root.right
            else:
                res.append(root.val)
                root = root.right
        return res
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
关闭