Java solution with O(1) memory+ O(n) time


  • 80
    T
    public class Solution {
        public void connect(TreeLinkNode root) {
            TreeLinkNode level_start=root;
            while(level_start!=null){
                TreeLinkNode cur=level_start;
                while(cur!=null){
                    if(cur.left!=null) cur.left.next=cur.right;
                    if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left;
                    
                    cur=cur.next;
                }
                level_start=level_start.left;
            }
        }
    }

  • 3
    L

    according to the Note of this question,
    Note:

    You may only use constant extra space.
    You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

    The method could return when cur.left == null


  • 2
    C

    @liopei19nn Being a perfect binary tree, I don't see the issue you are raising.


  • 0
    C

    This is very nice solution, thank you!


  • 0
    H
    This post is deleted!

  • 12
        public void connect(TreeLinkNode root) {
          if(root == null) return;    
          helper(root.left, root.right);    
        }
        
        void helper(TreeLinkNode node1, TreeLinkNode node2){
          if(node1 == null) return;    
          node1.next = node2;
          helper(node1.left, node1.right);
          helper(node2.left, node2.right);
          helper(node1.right, node2.left);
        }

  • 1
    B

    Can anyone explain why "level_start=level_start.left;" is needed in the end, please?


  • 0
    A

    @bigoffer4all it means level goes to next level. it's linked based on each level


  • 0
    R

    Javascript version:

    var connect = function(root) {
            
            var level_start = root;
            while(level_start != null) {
                var cur = level_start;
                while(cur != null) {
                    if(cur.left != null) cur.left.next = cur.right;
                    if(cur.right != null && cur.next != null) cur.right.next = cur.next.left;
                    cur = cur.next;
                }
                level_start = level_start.left;
            }
    };
    

  • 1

    @hot13399 recursion is not constant extra space solution...but using recursion looks much easier


  • 0
    B
    public class Solution {
        public void connect(TreeLinkNode root) {
            // level order traversal
            while (root != null) {
                TreeLinkNode start = root;
                TreeLinkNode prev = null;  // handle start.right.next = start.next.left
                while (start != null) {
                    if (prev != null) {
                        prev.next = start.left;
                    }
                    if (start.left != null) {
                        start.left.next = start.right;
                    } else {
                        return;  // since it is a perfect binary tree
                    }
                    prev = start.right;
                    start = start.next;
                }
                root = root.left;
            }
        }
    }
    

  • -1
    P

    this solution is not O(n) time


  • 0
    L
            TreeLinkNode root = new TreeLinkNode(1);
            root.left = new TreeLinkNode(2);
            root.right = new TreeLinkNode(3);
            root.left.right = new TreeLinkNode(5);
            root.right.left = new TreeLinkNode(6);
            root.right.right = new TreeLinkNode(7);
            root.left.right.left = new TreeLinkNode(8);
            root.left.right.right = new TreeLinkNode(9);
    

    I think your answer is not correct,for example above. Your answer is 8->next is null,but I think the correct answer is 8->next is 9.


Log in to reply
 

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