Java one pass recursive solution (12ms)


  • 0

    The key idea is to do to-down on left boundary node, then list all the leaf node as bottom boundary, and then bottom-up on right boundary. In order to trace down the left and right boundary, I used two boolean variables passed down to the children nodes. In addition, to prevent from duplication, each node can only be added to the list once. Thus, a local boolean variable added is used for above purpose.

    public class Solution {
        
        void helper(TreeNode root, boolean leftBound, boolean rightBound, List<Integer> ret) {
            if (root==null) return;
            boolean added = false;
            if (leftBound) { // left boundary
                ret.add(root.val);
                added=true;
            }
            if (root.left==null && root.right==null && ! added ) { //leaf node
                ret.add(root.val);
                return;
            } 
            if (root.left != null) { // go left first
                if (rightBound && root.right != null) // the left child is no longer a right boundary node
                    helper(root.left, leftBound, false, ret);
                else 
                    helper(root.left, leftBound, rightBound, ret);
            }
            if (root.right != null) { // go right
                if (leftBound && root.left != null) // the right child is no longer a left boundary node
                    helper(root.right, false, rightBound, ret);
                else 
                    helper(root.right, leftBound, rightBound, ret);
            }
            if (rightBound && ! added ) ret.add(root.val);
        }
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if (root==null) return new ArrayList<>();
            ret.add(root.val);
            helper(root.left, true, false, ret);
            helper(root.right, false, true, ret);
            return ret;
        }
    }
    

Log in to reply
 

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