@Test public void randomTest() { int N = 100000; Random r = new Random(); for (int i = 10; i < N; i += r.nextInt(i)) { TreeNode root = TreeNode.buildBT(i); List<TreeNode> res = InorderWithConstantSpace.solve(root); List<TreeNode> expect = expect(root); Assert.assertArrayEquals(expect.toArray(new TreeNode[0]), res.toArray(new TreeNode[0])); } }
public static List<TreeNode> solve(TreeNode root) { List<TreeNode> res = new ArrayList<>(); TreeNode p = root; while (p != null) { if (p.left == null) { res.add(p); p = p.right; continue; } boolean add = addOrRemoveLinkToParent(p, p.left); if (add) { p = p.left; } else { res.add(p); p = p.right; } } return res; }
InorderWithConstantSpace { public static List<TreeNode> solve(TreeNode root) { List<TreeNode> res = new ArrayList<>(); TreeNode p = root; while (p != null) { if (p.left == null) { res.add(p); p = p.right; continue; } boolean add = addOrRemoveLinkToParent(p, p.left); if (add) { p = p.left; } else { res.add(p); p = p.right; } } return res; } }
InorderWithConstantSpace { public static List<TreeNode> solve(TreeNode root) { List<TreeNode> res = new ArrayList<>(); TreeNode p = root; while (p != null) { if (p.left == null) { res.add(p); p = p.right; continue; } boolean add = addOrRemoveLinkToParent(p, p.left); if (add) { p = p.left; } else { res.add(p); p = p.right; } } return res; }  }
InorderWithConstantSpace { public static List<TreeNode> solve(TreeNode root) { List<TreeNode> res = new ArrayList<>(); TreeNode p = root; while (p != null) { if (p.left == null) { res.add(p); p = p.right; continue; } boolean add = addOrRemoveLinkToParent(p, p.left); if (add) { p = p.left; } else { res.add(p); p = p.right; } } return res; }  static List<TreeNode> solve(TreeNode root); }
InorderWithConstantSpace { public static List<TreeNode> solve(TreeNode root) { List<TreeNode> res = new ArrayList<>(); TreeNode p = root; while (p != null) { if (p.left == null) { res.add(p); p = p.right; continue; } boolean add = addOrRemoveLinkToParent(p, p.left); if (add) { p = p.left; } else { res.add(p); p = p.right; } } return res; }  static List<TreeNode> solve(TreeNode root);  }