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


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

  • 6
    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.


  • 1

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


  • 4
    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
    B
    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!

  • 0
    X

    @ctfu the problem says no duplicate nodes, not no duplicate values.


Log in to reply
 

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