My recursive solution(Java)


  • 63
    G
    public void connect(TreeLinkNode root) {
        if(root == null)
            return;
            
        if(root.left != null){
            root.left.next = root.right;
            if(root.next != null)
                root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
    }

  • 6
    A

    There questions required: You may only use constant extra space. Recurtion in this case will take more than constant extra space...


  • 6
    Y

    I have thought about this solution, but recursion uses stack, which I guess will take O(logN) space.


  • 0
    C

    Greate recursive! compare with my clumsy and time consuming one.

    /**
     * Definition for binary tree with next pointer.
     * struct TreeLinkNode {
     *  int val;
     *  TreeLinkNode *left, *right, *next;
     *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
     * };
     */
    class Solution {
        void dfs(TreeLinkNode* root,TreeLinkNode* p){
            if(!root || !root->left) return;
            
            root->left->next = root->right;
            if(p && p->right){
                p->right->next = root->left;
                dfs(root->left,p->right);
            }else{
                dfs(root->left,NULL);
            }
            dfs(root->right,root->left);
        }
    public:
        void connect(TreeLinkNode *root) {
            dfs(root,NULL);
        }
    };
    

  • 3
    F

    Great idea! I love this recursive version, I really do! I did try to come up with a recursive solution, but I was stuck with passing both left and right children to a helper method. Your idea is really brilliant.


  • 0
    A

    What will the time complexity be using recursion? Is it O(n) to add all the nodes to stack?


  • 0

    @gnayoaix my solution is exactly the same as yours!


  • 1
    L

    Here is another O(n) time, O(logn) space recursive solution.

        public void connect(TreeLinkNode root) {
            if(root == null) return;
            helper(root.left, root.right);
        }
        
        public void helper(TreeLinkNode left, TreeLinkNode right){
            if(left == null || left.next == right) return;   // skip repeated sub-problems
            left.next = right;
            helper(left.left, left.right);
            helper(left.right, right.left);
            helper(right.left, right.right);
        }
    

  • 2
    L

    This is actually O(1) stack space in most languages as the compilers optimize to reuse the recursive stack. You guys need to look at what is called Tail Recursion. Unfortunately, the Java compiler does not optimize this way.


  • 0
    H

    @leogogogo I really don't think it is O(n) time. There is repeat calculation in your code.


  • 0
    R

    C++ version:

    class Solution {
    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);
        }
    };
    

  • 0
    Y

    @hello_world_ so what is the time complexity as your opinion


  • 1

    Similar solution:

    void connect(TreeLinkNode root) {
      if (root == null || root.left == null) return;
    
      root.left.next = root.right;
      if (root.next != null)
        root.right.next = root.next.left;
        
      Stream.of(root.left, root.right).forEach(this::connect);
    }
    

  • 1
    T

    A iterative solution

        public void connect(TreeLinkNode root){
            if (null == root){
                return;
            }
    
            Queue<TreeLinkNode> queue = new LinkedList<>();
            queue.offer(root);
            queue.offer(null);
    
            while (!queue.isEmpty()){
                TreeLinkNode visit = queue.poll();
                if (null != visit){
                    visit.next = queue.peek();
                    queue.offer(visit.left);
                    queue.offer(visit.right);
                }else {
                    queue.offer(null);
                    if (queue.peek() == null){
                        break;
                    }
                }
            }
        }
    
    

  • 1
    G

    @anat By extra space usually it refers to not using any additional data Structure. Though you can clarify this with the Interviewer


  • 0
    F

    By far the easiest to understand solution (and most elegant)! Bravo!

    And if anyone is concerned about implicit stack frame space violating O(1), then since this is tail recursive this can be converted to an iterative solution.

    Since it's only implicit O(log n) space, it's really not that space consumptive in the long run anyway.


  • 0
    G

    Personally I think this is the best solution, but is recursion using constant extra space?
    What's the time complexicity here?


  • 0
    G

    @fahsrouq Space complexicity is logN, so I guess here, it's actually the "height" of the tree?


  • 0
    F

    My DFS version

    public class Solution {
        public void connect(TreeLinkNode root) {
            helper(root, new ArrayList(), 0);
        }
        public void helper(TreeLinkNode root, List<TreeLinkNode> list, int depth) {
            if (root == null) {
                return;
            }
            if (depth == list.size()) {
                list.add(root);
            } else {
                TreeLinkNode pre = list.get(depth);
                pre.next = root;
                list.set(depth, root);
            }
            helper(root.left, list, depth + 1);
            helper(root.right, list, depth + 1);
        }
    }
    

Log in to reply
 

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