Java O(1) solution


  • 0
    S
    public class Solution {
        
        private TreeLinkNode visitNode;
        private int left;
        private int right;
        
        public void connect(TreeLinkNode root) {
            TreeLinkNode lastLevelFirstNode = root;
            TreeLinkNode currentLevelFirstNode;
            TreeLinkNode p;
            TreeLinkNode q;
            while(lastLevelFirstNode != null) {
                visitNode = lastLevelFirstNode;
                left = 0;
                right =0;
                currentLevelFirstNode = getNextUnlinkedNode();
                p = currentLevelFirstNode;
                while(hasNext()){
                  q = getNextUnlinkedNode();
                  p.next = q;
                  p = q;
                }
                lastLevelFirstNode = currentLevelFirstNode;
            }
        }
        
        private TreeLinkNode getNextUnlinkedNode(){
            TreeLinkNode p = visitNode;
            while(p != null){
                if(left == 0){
                     left = 1;
                     if(p.left != null){
                        visitNode = p;
                        return p.left; 
                     }
                }
                else if(right == 0){
                    right = 1;
                    if(p.right != null){
                        left = 0;
                        right = 0;
                        visitNode = p.next;
                        return p.right;
                    }
                }
                if(left == 1 && right == 1){
                    p = p.next;
                    left = 0;
                    right = 0;
                }
            }
            visitNode = null;
            return null;
        }
        
        private boolean hasNext(){
            TreeLinkNode p = visitNode;
            int tmpLeft = left;
            int tmpRight = right;
            while(p != null){
                if(tmpLeft == 0){
                     tmpLeft = 1;
                     if(p.left != null){
                        left = 0;
                        right = 0;
                        visitNode = p;
                        return true; 
                     }
                }
                else if(tmpRight == 0){
                    tmpRight = 1;
                    if(p.right != null){
                        left = 1;
                        visitNode = p;
                        return true;
                    }
                }
                if(tmpLeft == 1 && tmpRight == 1){
                    p = p.next;
                    tmpLeft = 0;
                    tmpRight = 0;
                }
            }
            return false;
        }
    }
    

    The key of this solution is when you try to connect current level nodes ,last level nodes is connected.


Log in to reply
 

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