@@ -0,0 +1,1737 @@
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0Apublic class Inorder %7B%0A  static class TreeNode %7B%0A    int val;%0A    TreeNode parent;%0A    TreeNode left;%0A    TreeNode right;%0A%0A    TreeNode(int val, TreeNode left, TreeNode right) %7B%0A      this.val = val;%0A      this.left = left;%0A      this.right = right;%0A%0A      if (left != null) left.parent = this;%0A      if (right != null) right.parent = this;%0A    %7D%0A%0A    @Override%0A    public String toString() %7B%0A      return %22%5B%22 + val + %22%5D%22;%0A    %7D%0A  %7D%0A%0A  private static void inorder(TreeNode root, List%3CInteger%3E values) %7B%0A    if (root == null) return;%0A    inorder(root.left, values);%0A    values.add(root.val);%0A    inorder(root.right, values);%0A  %7D%0A%0A  private static void inorderConstant(TreeNode root, List%3CInteger%3E values) %7B%0A    TreeNode prev = null;%0A    TreeNode curr = root;%0A%0A    while (curr != null) %7B%0A      if (curr.left != null && curr.parent == prev) %7B%0A        prev = curr;%0A        curr = curr.left;%0A      %7D else if (curr.right != null && curr.right != prev) %7B%0A        values.add(curr.val);%0A        prev = curr;%0A        curr = curr.right;%0A      %7D else %7B%0A        if (curr.right != prev) %7B%0A          values.add(curr.val);%0A        %7D%0A        prev = curr;%0A        curr = curr.parent;%0A      %7D%0A    %7D%0A  %7D%0A%0A  public static void main(String%5B%5D args) %7B%0A    List%3CInteger%3E values = new ArrayList%3CInteger%3E();%0A%0A    TreeNode root = new TreeNode(5,%0A      new TreeNode(3,%0A        new TreeNode(2, null, null),%0A        new TreeNode(4, null, null)%0A      ),%0A      new TreeNode(7,%0A        new TreeNode(6, null, null),%0A        new TreeNode(8, null, null)%0A      )%0A    );%0A%0A    inorder(root, values);%0A    System.out.println(values);%0A    values.clear();%0A    inorderConstant(root, values);%0A    System.out.println(values);%0A  %7D%0A%7D%0A

add constant space inorder traversal