0ms Java Solution not only for perfect binary tree. (A more general solution)


  • 0

    Well, I wrote a code for the non-perfect binary tree. The code passed the testing case for the perfect one. But it is not tested for the non-perfect one. If any people want to discuss it here, welcome!
    Here is the situation this code can handle.
    If there is a binary tree like:

              0
          1      2
       3    4       5
    

    The next of 4 will be pointed to 5 not null.
    So the answer will become [0,null,1,2,null,3,4,5,null].
    Here is my code.

    public void connect(TreeLinkNode root) {
        pointtonext(root,null,0);
    }
    private void pointtonext(TreeLinkNode curr, TreeLinkNode parent, int lr){ //lr = 0 means left child
        if(curr==null) return;
        if(parent == null){//the root
            curr.next = null;
            pointtonext(curr.left,curr,0);
            pointtonext(curr.right,curr,1);
            return;
        }
        if(lr == 0){//left child
            if(parent.right!=null){
                curr.next = parent.right;
                pointtonext(curr.left,curr,0);
                pointtonext(curr.right,curr,1);
                return;
            }
        }
        TreeLinkNode temp = parent.next;
        while(temp!=null){ //Check all the parent's siblings
            if(temp.left!=null){
                curr.next = temp.left;
                break;
            }
            if(temp.right!=null){
                curr.next = temp.right;
                break;
            }
            temp = temp.next;
        }
        if(temp==null){//no parent's sibling have the children to be pointed to. (No cousins)
            curr.next = null;
        }
        pointtonext(curr.left,curr,0);
        pointtonext(curr.right,curr,1);
    }

Log in to reply
 

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