Beautiful Java solution includes tail recursion and constant space traversal implementation


  • 1
    Z
    // 116. Populating Next Right Pointers in Each Node
    // https://leetcode.com/problems/populating-next-right-pointers-in-each-node/#/description
    
    /**
     * Definition for binary tree with next pointer.
     * public class TreeLinkNode {
     *     int val;
     *     TreeLinkNode left, right, next;
     *     TreeLinkNode(int x) { val = x; }
     * }
     */
    
    // Tail Recursion solution. 
    // Although it seems like constant space because tail recursion optimization;
    //  however, Java does not optimize tail recursion so it requires O(logN) space.
    public class Solution {
        public void connect(TreeLinkNode root) {
            if (root == null)
                return;
            root.next = null;
            dfs(root);
        }
        
        public void dfs(TreeLinkNode root){
            if (root.left != null){
                root.left.next = root.right;
                if (root.next != null){
                    root.right.next = root.next.left;
                }
                dfs(root.left);
                dfs(root.right);
            }
        }
    }
    
    // Constanst space solution
    // Construct connection from the parent node point of view
    // We can leverage the next pointer to traverse the tree without referencing parent node.
    public class Solution {
        public void connect(TreeLinkNode root) {
            TreeLinkNode nextRowStart = root;
            while (nextRowStart != null){
                TreeLinkNode cursor = nextRowStart;
                while (cursor != null){
                    if (cursor.left != null){
                        cursor.left.next = cursor.right;
                        if (cursor.next != null){
                            cursor.right.next = cursor.next.left;
                        }
                    }
                    cursor = cursor.next;
                }
                nextRowStart = nextRowStart.left;
            }
        }
    }
    

  • 0
    O

    How come this beautiful solution doesn't have any upvotes?!


Log in to reply
 

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