经典递归做法

 public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        process(root, list);
        return list;
    }
    private void process(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        process(node.left, list);
        list.add(node.val);
        process(node.right, list);
    }
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

迭代做法

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

Morris遍历

 public static void morrisIn(Node head) {
        if (head == null) {
            return;
        }
        Node cur = head;
        Node mostRight = null;
        while (cur != null) {
            // cur 有没有左树
            mostRight = cur.left;
            if (mostRight != null) { // 有左树的情况下
                // 找到cur左树上，真实的最右
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                // 从while出来， mostRight一定是cur左树上的最右节点
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // mostRight.right --> cur
                    mostRight.right = null;
                    System.out.println(cur.value + " ");
                }
            }
            cur = cur.right;
        }
    }
    public static class Node {
        public int value;
        Node left;
        Node right;
        public Node(int data) {
            this.value = data;
        }
    }