Java Preorder Single Pass O(n) Solution


  • 11

    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) {
        List<Integer> left = new LinkedList<>(), right = new LinkedList<>();
        preorder(root, left, right, 0);
        left.addAll(right);
        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);
    }
    

  • 0
    This post is deleted!

  • 0

    @luming89 Oh sorry, I meant preorder. Thanks!


  • -1
    H
    This post is deleted!

  • 0

    @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).


  • 0
    H

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


  • 0
    R

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


  • 1

    Add some comments to make the logic more clearly.

    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            //corner case
            List<Integer> list = new ArrayList<>();
            if (root == null) {
                return list;
            }
    
            list.add(root.val);
    
            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) {
                list.add(root.val);
            }
    
            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) {
                list.add(root.val);
            }
    
            dfs(root.right, isLeftBound && root.left == null, isRightBound, list);
    
            //take care of rightBorder elements in postOrder
            if (isRightBound) {
                list.add(root.val);
            }
        }
    }
    

  • 0

    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);
    }

Log in to reply
 

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