@Test public void basicTest2() { TreeNode root = new TreeNode(1); root.left = new TreeNode(-2); root.left.right = new TreeNode(-3); List<TreeNode> res = InorderWithConstantSpace.solve(root); Assert.assertEquals(3, res.size()); Assert.assertEquals(root.left, res.get(0)); Assert.assertEquals(root.left.right, res.get(1)); Assert.assertEquals(root, res.get(2)); }
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);  }