My short and straightforward java solution


  • 0
    Y
    /**
     * 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) return;
            TreeLinkNode begin = root, cur;
            while (begin != null) {
                cur = begin;
                begin = null;  // set begin to the left most child in the following code
                while (cur != null) {
                    // if/elseif statements that can be improved to be cleaner
                    if (cur.left != null && cur.right != null) {
                        cur.left.next = cur.right;
                        cur.right.next = getNextChild(cur.next);
                        if (begin == null) {
                            begin = cur.left;
                        }
                    } else if (cur.left != null) {
                        cur.left.next = getNextChild(cur.next);
                        if (begin == null) {
                            begin = cur.left;
                        }
                    } else if (cur.right != null) {
                        cur.right.next = getNextChild(cur.next);
                        if (begin == null) {
                            begin = cur.right;
                        }
                    } else { // both left & right children are null
                        // do nothing
                    }
                    cur = cur.next;
                }
            }
        }
        
        private TreeLinkNode getNextChild(TreeLinkNode root) {
            if (root == null) {
                return null;
            }
            // loop to find the next node (if there is one)
            while (root != null && root.left == null && root.right == null) {
                root = root.next;
            }
            if (root == null) {  // cannot find the next node
                return null;
            } else {
                return root.left != null ? root.left : root.right;
            }
        }
    }
    

Log in to reply
 

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