94. 二叉树的中序遍历

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

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function inorderTraversal(root: TreeNode | null): number[] {
    return root === null ? [] : [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
};

function inorderTraversal2(root: TreeNode | null): number[] {
    const res = [];
    while(root){
        if(root.left){
            let pre = root.left;
            while(pre.right && pre.right !== root){
                pre = pre.right;
            }
            if(pre.right === null){
                pre.right = root;
                root = root.left;
                continue;
            }
            pre.right = null;
        }
        res.push(root.val);
        root = root.right;
    }
    return res;
};

思路

方法一：递归法

最简洁的实现方式，利用递归的特性：

1. 递归遍历左子树
2. 访问根节点
3. 递归遍历右子树

使用扩展运算符 ... 将结果合并成一个数组。

• 时间复杂度 $O(n)$，其中 $n$ 是节点数量
• 空间复杂度 $O(n)$，递归调用栈的深度

方法二：Morris 遍历

Morris 遍历是一种不使用递归和栈的遍历方法，空间复杂度为 $O(1)$：

1. 如果当前节点的左子树存在：
   • 找到左子树的最右节点（前驱节点）
   • 如果前驱节点的右指针为空，将其指向当前节点（建立线索），然后移动到左子节点
   • 如果前驱节点的右指针已经指向当前节点，说明左子树已遍历完，断开线索，访问当前节点，移动到右子节点
2. 如果当前节点的左子树不存在：
   • 访问当前节点
   • 移动到右子节点

• 时间复杂度 $O(n)$
• 空间复杂度 $O(1)$