题目：

94. 二叉树的中序遍历

题解：

1. 递归中序遍历：

第一种解决方法是使用递归。这是经典的方法，直截了当。我们可以定义一个辅助函数来实现递归。

2. 迭代中序遍历：

考查到当前节点时，并不直接输出该节点。

而是当考查节点为空时，从栈中弹出的时候再进行输出(永远先考虑左子树，直到左子树为空才访问根节点)。

思路：

每到一个节点 A，因为根的访问在中间，将 A 入栈。然后遍历左子树，接着访问 A，最后遍历右子树。

在访问完 A 后，A 就可以出栈了。因为 A 和其左子树都已经访问完成。

栈S;
p= root;
while(p || S不空){
    while(p){
        p入S;
        p = p的左子树;
    }
    p = S.top 出栈;
    访问p;
    p = p的右子树;
}

代码：

引入模板：

1. ConstructTree.java

import java.util.Deque;
import java.util.LinkedList;

public class ConstructTree {
    // 从数组形式创建一棵树
    public static TreeNode constructTree(Integer[] nums) {
        if (nums.length == 0)
            return new TreeNode(0);
        Deque<TreeNode> nodeQueue = new LinkedList<>();
        // 创建一个根节点
        TreeNode root = new TreeNode(nums[0]);
        nodeQueue.offer(root);
        TreeNode cur;
        // 记录当前行节点的数量（注意不一定是2的幂，而是上一行中非空节点的数量乘2）
        int lineNodeNum = 2;
        // 记录当前行中数字在数组中的开始位置
        int startIndex = 1;
        // 记录数组中剩余的元素的数量
        int restLength = nums.length - 1;

        while (restLength > 0) {
            // 只有最后一行可以不满，其余行必须是满的
            // // 若输入的数组的数量是错误的，直接跳出程序
            // if (restLength < lineNodeNum) {
            // System.out.println("Wrong Input!");
            // return new TreeNode(0);
            // }
            for (int i = startIndex; i < startIndex + lineNodeNum; i = i + 2) {
                // 说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
                if (i == nums.length)
                    return root;
                cur = nodeQueue.poll();
                if (nums[i] != null) {
                    cur.left = new TreeNode(nums[i]);
                    nodeQueue.offer(cur.left);
                }
                // 同上，说明已经将nums中的数字用完，此时应停止遍历，并可以直接返回root
                if (i + 1 == nums.length)
                    return root;
                if (nums[i + 1] != null) {
                    cur.right = new TreeNode(nums[i + 1]);
                    nodeQueue.offer(cur.right);
                }
            }
            startIndex += lineNodeNum;
            restLength -= lineNodeNum;
            lineNodeNum = nodeQueue.size() * 2;
        }

        return root;
    }

    public static void preOrder(TreeNode root) {// 前序排列
        if (root == null)
            return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void midOrder(TreeNode root) {// 中序排列
        if (root == null)
            return;
        midOrder(root.left);
        System.out.print(root.val + " ");
        midOrder(root.right);
    }

    public static void aftOrder(TreeNode root) {// 后序排列
        if (root == null)
            return;
        aftOrder(root.left);
        aftOrder(root.right);
        System.out.print(root.val + " ");
    }
}

2. TreeOperation.java

// TreeOperation.java
public class TreeOperation {
    /* 树的结构示例： 1 / \ 2 3 / \ / \ 4 5 6 7 */
    
    // 用于获得树的层数
    public static int getTreeDepth(TreeNode root) {
        return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
    }

    private static void writeArray(TreeNode currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
        // 保证输入的树不为空
        if (currNode == null)
            return;
        // 先将当前节点保存到二维数组中
        res[rowIndex][columnIndex] = String.valueOf(currNode.val);

        // 计算当前位于树的第几层
        int currLevel = ((rowIndex + 1) / 2);
        // 若到了最后一层，则返回
        if (currLevel == treeDepth)
            return;
        // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
        int gap = treeDepth - currLevel - 1;

        // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
        if (currNode.left != null) {
            res[rowIndex + 1][columnIndex - gap] = "/";
            writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
        }

        // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
        if (currNode.right != null) {
            res[rowIndex + 1][columnIndex + gap] = "\\";
            writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
        }
    }

    public static void show(TreeNode root) {
        if (root == null)
            System.out.println("EMPTY!");
        // 得到树的深度
        int treeDepth = getTreeDepth(root);

        // 最后一行的宽度为2的（n - 1）次方乘3，再加1
        // 作为整个二维数组的宽度
        int arrayHeight = treeDepth * 2 - 1;
        int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
        // 用一个字符串数组来存储每个位置应显示的元素
        String[][] res = new String[arrayHeight][arrayWidth];
        // 对数组进行初始化，默认为一个空格
        for (int i = 0; i < arrayHeight; i++) {
            for (int j = 0; j < arrayWidth; j++) {
                res[i][j] = " ";
            }
        }

        // 从根节点开始，递归处理整个树
        // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
        writeArray(root, 0, arrayWidth / 2, res, treeDepth);

        // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
        for (String[] line : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < line.length; i++) {
                sb.append(line[i]);
                if (line[i].length() > 1 && i <= line.length - 1) {
                    i += line[i].length() > 4 ? 2 : line[i].length() - 1;
                }
            }
            System.out.println(sb.toString());
        }
    }
}

1. 递归法：

/** * code94 */

import java.util.*;

public class code94 {

    // 解法一：递归
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }

    public static void helper(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        helper(root.left, res);
        res.add(root.val);
        helper(root.right, res);
    }

    public static void main(String[] args) {
        // 根据给定的数组创建一棵树
        Integer nums[] = { 1, null, 2, 3 };
        TreeNode tree = ConstructTree.constructTree(nums);
        // 将刚刚创建的树打印出来
        TreeOperation.show(tree);

        // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
        // TreeNode tree = ConstructTree.constructTree(nums);
        // ConstructTree.preOrder(tree);
        // System.out.println();
        // ConstructTree.midOrder(tree);
        // System.out.println();
        // ConstructTree.aftOrder(tree);
        // System.out.println();

        // TreeOperation.show(tree);

        System.out.println("中序遍历：");
        List<Integer> list = inorderTraversal(tree);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }
}

2. 迭代法：

/** * code94 */

import java.util.*;

public class code94 {

    // 解法二：迭代
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
    
    public static void main(String[] args) {
        // 根据给定的数组创建一棵树
        Integer nums[] = { 1, null, 2, 3 };
        TreeNode tree = ConstructTree.constructTree(nums);
        // 将刚刚创建的树打印出来
        TreeOperation.show(tree);

        // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
        // TreeNode tree = ConstructTree.constructTree(nums);
        // ConstructTree.preOrder(tree);
        // System.out.println();
        // ConstructTree.midOrder(tree);
        // System.out.println();
        // ConstructTree.aftOrder(tree);
        // System.out.println();

        // TreeOperation.show(tree);

        System.out.println("中序遍历：");
        List<Integer> list = inorderTraversal(tree);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
    }    
}

参考：

二叉树遍历(先序、中序、后序)

1. 题解

1. 二叉树的中序遍历
2. 颜色标记法-一种通用且简明的树遍历方法
3. 二叉树的中序遍历 - 迭代法
4. Java栈迭代遍历
5. 迭代和递归
6. 请问 [1, null, 2, 3] 在二叉树测试用例中代表什么

2. 二叉树遍历算法

7. 二叉树遍历(先序、中序、后序)
8. 二叉树前序遍历、中序遍历、后序遍历、层序遍历的直观理解
9. 二叉树的先序、中序、后序遍历序列
10. [算法] 二叉树的 先序遍历、中序遍历、后序遍历
11. 二叉树的非递归遍历

3. java实现二叉树

12. 二叉树算法（java）
13. Java实现二叉树
14. 【Java】实现二叉树基本操作、面试题
15. 二叉树(java)