94. 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

代码【Morris遍历】

思路：使用前驱指针pre和root指针遍历整个二叉树

1、如果x无左孩子，先将x的值加入答案数组，再访问x的右孩子

2、如果x有左孩子，则找到x左子树上最右的节点，记为前驱pre

• 若pre.right == null，则将其右孩子指向x，然后访问x的左孩子
• 若pre.right != null，表明左子树处理完毕，将x的值加入答案数组，并将pre的右孩子置空，然后访问x的右孩子

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    TreeNode pre = null;
    while (root != null) {
        if (root.left != null) {    // 有左子树
            // 找当前节点的中序前驱
            pre = root.left;
            while (pre.right != null && pre.right != root) {
                pre = pre.right;
            }
            if (pre.right == null) {
                pre.right = root; // pre.right -> root，建立中序后继链
                root = root.left; // 继续处理左子树
            } else { // 当前节点的左子树处理完毕，当前节点直接压入，断开后继链
                ans.add(root.val);
                pre.right = null;
                root = root.right;  // 继续处理右子树
            }
        } else {    // 无左子树，当前节点直接压入
            ans.add(root.val);
            root = root.right;      // 继续处理右子树
        }
    }
    return ans;
}

代码【递归】

思路：

1、递归出口：root == null

2、中序遍历：左中右

• inorder(root.left)
• ans.add(root.val)
• inorder(root.right)

List<Integer> ans = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
    inorder(root);
    return ans;
}

private void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
    ans.add(root.val);
    inorder(root.right);
}

代码【迭代】

思路：栈用于存储左子树的元素

1、首先cur循环向左移动直到左子树的左边界上，路过的元素依次入栈

2、接着，一边退栈，一边对右子树进行相同的操作

3、直到栈中无元素或cur指针为空才结束迭代

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> ans = new ArrayList<>();
    Stack<TreeNode> st = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !st.isEmpty()) {
        while (cur != null) { // 左
            st.push(cur);
            cur = cur.left;
        }
        cur = st.pop();
        ans.add(cur.val); // 中
        cur = cur.right; // 右
    }
    return ans;
}

代码【迭代2】

思路：

1、先处理左子树，当cur.left != null，将cur.left加入栈中，并将其left指针置空

2、左子树处理完毕后，将cur.val加入结果集，并弹出栈顶元素

3、处理右子树，当cur.right != null，将cur.right加入栈

4、迭代出口：栈为空时，结束遍历过程

public List<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> ans = new ArrayList<>();
    Stack<TreeNode> st = new Stack<>();
    st.add(root);
    while (!st.isEmpty()) {
        TreeNode cur = st.peek();
        if (cur == null) {
            st.pop();
            continue;
        }
        if (cur.left != null) {    // 左
            st.add(cur.left);
            cur.left = null; 
            continue;
        }

        ans.add(cur.val);    // 中
        st.pop();
        if (cur.right != null) {    // 右
            st.add(cur.right);
        }
    }
    return ans;
}