Java recursive solution O(n) with O(1) extra space


  • 0
    A

    Hello, everyone!

    Here's my recursive java solution. The idea is to connect siblings of every parent node, then walk down and connect each border right node of the left subtree to the left border node of the right subtree (until to bottom is reached).

    Please, let me know if you there any mistake or flaw in my logic!

    Thanks,

    -Alex

    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public void connect(TreeLinkNode root) {
            if (root != null) {
                connect(root.left, root.right);
            }
        }
        
        private void connect(TreeLinkNode left, TreeLinkNode right) {
            if (left == null && right == null) return;
            
            connect(left.left, left.right);
            connect(right.left, right.right);
            
            while (left != null && right != null)
            {
                left.next = right;
                left = left.right;
                right = right.left;
            }
        }
    }
    

Log in to reply
 

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