Java easy to understand solution. Find half boundaries and half leaves first.


  • 0
    6

    The idea is very simple. We can find the boundaries and leaves in the left subtree first using recursion and put them into a list. And do the same to the right subtree. Using a flag findBoundry to check whether the current node is a boundary.
    The last two functions can be merged into one.

    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> lefthalf = new ArrayList<>();
            List<Integer> righthalf = new ArrayList<>();
            List<Integer> result = new ArrayList<>();
            if(root == null)
                return result;
            result.add(root.val);
            findleft(lefthalf, root.left, true);
            findright(righthalf, root.right, true);
            result.addAll(lefthalf);
            result.addAll(righthalf);
            return result;
        }
        
        public void findleft(List<Integer> list, TreeNode node, boolean findBoundary){
            if(node == null)
                return;
            if(findBoundary || node.left == null && node.right == null)
                list.add(node.val);
            findleft(list,node.left,findBoundary);
    	if(findBoundary && node.left == null)
    	    findleft(list,node.right,true);
    	else
    	    findleft(list,node.right,false);
        }
        public void findright(List<Integer> list, TreeNode node, boolean findBoundary){
            if(node == null)
                return;
            if(findBoundary || node.left == null && node.right == null)
                list.add(0, node.val);
            findright(list,node.right,findBoundary);
            if(findBoundary && node.right == null)
                findright(list,node.left,true);
            else
                findright(list,node.left,false);
        }
    }
    '''

Log in to reply
 

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