Java Preorder Single Pass O(n) Solution

• We perform a single preorder traversal of the tree, keeping tracking of the left boundary and middle leaf nodes and the right boundary nodes in the process. A single flag is used to designate the type of node during the preorder traversal. Its values are:
0 - root, 1 - left boundary node, 2 - right boundary node, 3 - middle node.

``````public List<Integer> boundaryOfBinaryTree(TreeNode root) {
preorder(root, left, right, 0);
return left;
}

public void preorder(TreeNode cur, List<Integer> left, List<Integer> right, int flag) {
if (cur == null) return;
if (flag == 2) right.add(0, cur.val);
else if (flag <= 1 || cur.left == null && cur.right == null) left.add(cur.val);
preorder(cur.left, left, right, flag <= 1 ? 1 : (flag == 2 && cur.right == null) ? 2 : 3);
preorder(cur.right, left, right, flag % 2 == 0 ? 2 : (flag == 1 && cur.left == null) ? 1 : 3);
}
``````

• This post is deleted!

• @luming89 Oh sorry, I meant preorder. Thanks!

• This post is deleted!

• @hakem In a linked list, adding to the beginning or end of a list or concatenating two lists can be done in O(1) (assuming the data structure maintains pointers to both ends of list).

• @compton_scatter Oh sorry I didn't notice that it was a linked list

• @compton_scatter
If we use ArrayList and reverse "right" list before add it at the end of "left" list, it will be more efficient.

``````public class Solution {
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
//corner case
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}

dfs(root.left, true, false, list);//left half tree
dfs(root.right, false, true, list);//right half tree

return list;
}

//PreOrder on the left half tree to fetch left Border elements, InOrder on the left and right half tree to fetch leaf elements PostOrder on the right half tree to fetch right Border elements
private void dfs(TreeNode root, boolean isLeftBound, boolean isRightBound, List<Integer> list) {
//base case
if (root == null) {
return;
}

//take care of leftBorder elements in preOrder
if (isLeftBound) {
}

dfs(root.left, isLeftBound, isRightBound && root.right == null, list);

//take care of leaf nodes in AnyOrder, I just use InOrder
if (!isLeftBound && !isRightBound && root.left == null && root.right == null) {
}

dfs(root.right, isLeftBound && root.left == null, isRightBound, list);

//take care of rightBorder elements in postOrder
if (isRightBound) {
}
}
}
``````

• it's really a great and clear solution
how about putting the right.add() to the end just like a postorder traverse?

``````public void preorder(TreeNode cur, List<Integer> left, List<Integer> right, int flag) {
if (cur == null) return;
else if (flag <= 1 || (flag != 2 && cur.left == null && cur.right == null)) left.add(cur.val);
preorder(cur.left, left, right, flag <= 1 ? 1 : (flag == 2 && cur.right == null) ? 2 : 3);
preorder(cur.right, left, right, flag % 2 == 0 ? 2 : (flag == 1 && cur.left == null) ? 1 : 3);
if (flag == 2) right.add(0, cur.val);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.