// preorder property
boolean seeLeaf = false;
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) return res;
res.add(root.val);
if (root.left != null) {
preOrder(root.left, res);
}
List<Integer> revRes = new ArrayList<>();
seeLeaf = false;
if (root.right != null) {
revPreOrder(root.right, revRes);
}
for (int i = revRes.size()1; i >= 0; i) {
res.add(revRes.get(i));
}
return res;
}
private void preOrder(TreeNode root, List<Integer> res) {
if (root.left == null && root.right == null) {
res.add(root.val);
seeLeaf = true;
return;
}
if (!seeLeaf) res.add(root.val);
if (root.left != null) {
preOrder(root.left, res);
}
if (root.right != null) {
preOrder(root.right, res);
}
}
private void revPreOrder(TreeNode root, List<Integer> res) {
if (root.left == null && root.right == null) {
res.add(root.val);
seeLeaf = true;
return;
}
if (!seeLeaf) res.add(root.val);
if (root.right != null) {
revPreOrder(root.right, res);
}
if (root.left != null) {
revPreOrder(root.left, res);
}
}
PreOrder O(n) check everynode only once


@bitlearn By my algorithm, it return [1,2,4,6,7,3]. Actually, in my algorithm, the postOrder is not standard, This name can cause confusion. The postOrder of my algorithm is to check root firstly, then check root.right check root.left, you can think it equals with preOrder on the tree which is generated by that you exchange left/right subtree in originally tree recursively.
Other thing I want to say is that I think this problem is to test the preOrder property which is before reaching
first leaf, the nodes you checked are left boundary nodes in this problem.No matter any order (pre, post, in) you check tree, the leafs you checked is from left to right.
For right boundary, you could image that you exchange the left, right subtree recursively, then preOrder check on this changed tree can give you the right boundary but it is reversed.