Recursive approach without using 'next pointer' to traverse! O(1) space & O(n) time


  • 0
    K
    public class Solution {
        public void connect(TreeLinkNode root) {
            if(root == null || (root.left == null && root.right == null)) return;
            // Traverse to the bottom of the tree
            connect(root.left);
            connect(root.right);
            // Connect left to right
            root.left.next = root.right;
            // Connect the right nodes of left subtree with left nodes of right subtree
            connectInnerNodes(root.left, root.right);
        }
        
        private void connectInnerNodes(TreeLinkNode root1, TreeLinkNode root2) {
            if(root1 != null && root2 != null && root1.right != null && root2.left != null) {
                root1.right.next = root2.left;
                connectInnerNodes(root1.right, root2.left);
            }
        }
    }
    

Log in to reply
 

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