二叉树的中序遍历「变题」

94. 二叉树的中序遍历

开头先来一个小插曲，关于「二叉树遍历」相关的总结可见 二叉树遍历

// 递归
// 时间复杂度 : O(n)
// 空间复杂度 : O(n) -> 递归栈
private List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    traversal(root);
    return ans;
}
private void traversal(TreeNode root) {
    if (root == null) return ;
    traversal(root.left);
    ans.add(root.val);
    traversal(root.right);
}

// 非递归
// 时间复杂度 : O(n)
// 空间复杂度 : O(n) -> 辅助栈
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Deque<TreeNode> st = new ArrayDeque<>();
    while (!st.isEmpty() || root != null) {
        while (root != null) {
            st.push(root);
            root = root.left;
        }
        TreeNode top = st.poll();
        ans.add(top.val);
        root = top.right;
    }
    return ans;
}

// 莫里斯
// 时间复杂度 : O(n)
// 空间复杂度 : O(1)
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    while (root != null) {
        if (root.left != null) {
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            }
            pre.right = root;
            TreeNode tmp = root;
            root = root.left;
            tmp.left = null;
        } else {
            ans.add(root.val);
            root = root.right;
        }
    }
    return ans;
}