Boundary of Binary Tree


Pls check out my recursive solution. It does this in one iteration.
https://discuss.leetcode.com/topic/87069/javarecursivesolutionbeats94

@tyuan73 root node doesn't have a right child, then according to the definition of right boundary only root node will be considered in right node. Hence 4 should not be there.

Small typo in "The current node is a root node: In this case, the right child will always be a left boundary node. e.g. relationship between A & C in the above figure."
It should say "The current node is a root node: In this case, the right child will always be a RIGHT boundary node. e.g. relationship between A & C in the above figure."

Just making "Approach #2 Using PreOrder Traversal" a bit simple as below (accepted):
public class Solution { enum Flag {ROOT, LEFT, RIGHT, MIDDLE}; public List<Integer> boundaryOfBinaryTree(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> leftBoundary = new ArrayList<>(); List<Integer> leaves = new ArrayList<>(); List<Integer> rightBoundary = new ArrayList<>(); preOrder(root, leftBoundary, leaves, rightBoundary, Flag.ROOT); leftBoundary.addAll(leaves); leftBoundary.addAll(rightBoundary); return leftBoundary; } // root > left > right private void preOrder(TreeNode root, List<Integer> leftBoundary, List<Integer> leaves, List<Integer> rightBoundary, Flag flag) { if (root == null) { return; } //Root if (flag == Flag.ROOT  flag == Flag.LEFT) { leftBoundary.add(root.val); } else if (flag == Flag.RIGHT) { rightBoundary.add(0, root.val); } else if (root.left == null && root.right == null) { leaves.add(root.val); } //Left if (root.left != null) { preOrder(root.left, leftBoundary, leaves, rightBoundary, childFlag(root, flag, true)); } //Right if (root.right != null) { preOrder(root.right, leftBoundary, leaves, rightBoundary, childFlag(root, flag, false)); } } private Flag childFlag(TreeNode parent, Flag flag, boolean isLeftChild) { if (flag == Flag.ROOT) { return isLeftChild ? Flag.LEFT : Flag.RIGHT; } //Parent on left boundary, if exist left child, the right child should be a middle node if (flag == Flag.LEFT && !isLeftChild && parent.left != null) { return Flag.MIDDLE; } //Parent on right boundary, if exist right node, the left child should be a middle node. if (flag == Flag.RIGHT && isLeftChild && parent.right != null) { return Flag.MIDDLE; } return flag; } }