Intuitive recursive soln - Java ~11ms


  • 0
    S

    Concat left boundary, leaves & (reverse of ) right boundary

    class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            if(root == null) return new ArrayList<Integer>();
    
            List<Integer> boundary = new ArrayList<>(); 
            boundary.add(root.val);
            
            List<Integer> left = new ArrayList<>();
            getLeftBoundary(root.left, left);
            boundary.addAll(left);
            
            List<Integer> leaves = new ArrayList<>();
            getLeaves(root.left, leaves);
            getLeaves(root.right, leaves);
            boundary.addAll(leaves);
            
            List<Integer> right = new ArrayList<>();
            getRightBoundary(root.right, right);
            Collections.reverse(right);
            boundary.addAll(right);
            
            return boundary;
        }
        
        private void getLeftBoundary(TreeNode node, List<Integer> list){
            if(node == null || (node.left ==null && node.right ==null)){
                return;
            }
            
            list.add(node.val);
            if(node.left !=null){
                getLeftBoundary(node.left, list);
            } else{
                getLeftBoundary(node.right, list);
            }
        }
        
        private void getLeaves(TreeNode node, List<Integer> list){
            if(node == null){
                return;
            }
            
            if(node.left == null && node.right ==null){
                list.add(node.val);
                return;
            }
            
            getLeaves(node.left, list);
            getLeaves(node.right, list);
        }
        
        
        private void getRightBoundary(TreeNode node, List<Integer> list){
            if(node == null || (node.left ==null && node.right ==null)){
                return;
            }
            
            list.add(node.val);
            if(node.right !=null){
                getRightBoundary(node.right, list);
            } else{
                getRightBoundary(node.left, list);
            }
        }
    }
    

Log in to reply
 

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