Java(12ms) - left boundary, left leaves, right leaves, right boundary


  • 40
    List<Integer> nodes = new ArrayList<>(1000);
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        
        if(root == null) return nodes;
    
        nodes.add(root.val);
        leftBoundary(root.left);
        leaves(root.left);
        leaves(root.right);
        rightBoundary(root.right);
        
        return nodes;
    }
    public void leftBoundary(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return;
        nodes.add(root.val);
        if(root.left == null) leftBoundary(root.right);
        else leftBoundary(root.left);
    }
    public void rightBoundary(TreeNode root) {
        if(root == null || (root.right == null && root.left == null)) return;
        if(root.right == null)rightBoundary(root.left);
        else rightBoundary(root.right);
        nodes.add(root.val); // add after child visit(reverse)
    }
    public void leaves(TreeNode root) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            nodes.add(root.val);
            return;
        }
        leaves(root.left);
        leaves(root.right);
    }

  • 4
    Z

    wow~ brilliant to use

        leaves(root.left);
        leaves(root.right);
    

    I tried similar idea to use leaves(root) and then remove the duplicate node with left and right boundary, but there are several corner cases hard to deal with.


  • 0

    The idea is brilliant and the structure is crystal clear, this is what solution you may come up with during an interview!


  • 3
    G

    Nice solution! Please check-out my recursive Java solution which takes 11ms and beats 94% Java Solutions.

    public class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> ls = new ArrayList<Integer>();
            if(root!=null){
                ls.add(root.val);
                lookupElems(root.left,ls,true,false);      
                lookupElems(root.right,ls,false,true);
            }
            return ls;
        }
        
        private void lookupElems(TreeNode root,List<Integer> ls,boolean isLeftBoundary,boolean isRightBoundary){
            if (root==null) {
                return;
            }
            if (root.left==null && root.right==null) {
                ls.add(root.val);
                return;
            }        
            if (isLeftBoundary) {
                ls.add(root.val);
            } 
            lookupElems(root.left,ls,root.left!=null && isLeftBoundary,root.right==null && isRightBoundary);
            lookupElems(root.right,ls,root.left==null && isLeftBoundary,root.right!=null && isRightBoundary);
            if (isRightBoundary) {
                ls.add(root.val);
            }
        }
    }
    

    Step by step approach here - https://discuss.leetcode.com/topic/87069/java-recursive-solution-beats-94


  • 0

    Nice solution. Very easy to understand and flow is elegant. There is another solution that can traverse the tree only once.


  • 0
    J

    @jaqenhgar
    Please check this input: [1,2,3,null, null, 4, null, 5, 8, 6,7,null,9]
    Your output is [1,2,6,7,9,8,4,3]. However, this is the not the boundary of the tree.
    The right one should be [1,2,5,6,7,9,8,4,3] or [1,2,4,5,6,7,9,8,3].

    The definition of the boundary by OJ is incorrect here.


  • 0
    Y

    Hi @ganesh9 I have almost the same solution as yours~


  • 0
    P

    Slightly modified version which eliminates the 2 calls to leaves(root). I did not find that necessary.

    List<Integer> nodes = new ArrayList<>(1000);
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {

    if(root == null) return nodes;
    if (root.left != null || root.right != null)
        nodes.add(root.val);
    
    leftBoundary(root.left);
    leaves(root);
    rightBoundary(root.right);
    
    return nodes;
    

    }


  • 0
    C

    Do anybody know why my output for this case wrong? Why the OJ output here can contains duplicate? Isn't the question requires no duplicate?
    0_1499219024355_Screen Shot 2017-07-04 at 8.40.02 PM.png


  • 0
    C

    @ctfu I have figured out myself.
    What the question mean by no duplicate it actually means there is no duplicate inclusion of the connecting elements between boundaries. I don't know if is just me, but the question's definition about no duplicates does throw me off.


  • 0
    T
    This post is deleted!

  • 0
    This post is deleted!

  • 0
    F

    if(root == null || (root.left == null && root.right == null)) return;
    This condition is very smart. Avoid adding leftmost leaf node and rightmost leaf node while traverse left and right boundary.


  • 0
    This post is deleted!

Log in to reply
 

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