4ms slow but easy to understand java solution


  • 0
    S

    Each time we find the right most child of level i of root's left child and the left most child of level i of root's right child and connect them and go down recursively.

    public void connect(TreeLinkNode root) {
            if(root == null || (root.left == null && root.right == null)) return;
            int i = 0;
            TreeLinkNode n1 = rightMost(root.left, 0, 0);
            TreeLinkNode n2 = leftMost(root.right, 0, 0);
            while(n1 != null && n2 != null){
                i++;
                n1.next = n2;
                n1 = rightMost(root.left, 0, i);
                n2 = leftMost(root.right, 0, i);
            }
            connect(root.left);
            connect(root.right);
        }
        private TreeLinkNode rightMost(TreeLinkNode node, int depth, int max){
            if(node == null) return null;
            if(depth == max) return node;
            if(depth < max && node.left == null && node.right == null) return null;
            TreeLinkNode temp = rightMost(node.right, depth + 1, max);
            if(temp == null) temp = rightMost(node.left, depth + 1, max);
            else return temp;
            if(temp == null) return null;
            return temp;
        }
        private TreeLinkNode leftMost(TreeLinkNode node, int depth, int max){
            if(node == null) return null;
            if(depth == max) return node;
            if(depth < max && node.left == null && node.right == null) return null;
            TreeLinkNode temp = leftMost(node.left, depth + 1, max);
            if(temp == null) temp = leftMost(node.right, depth + 1, max);
            else return temp;
            if(temp == null) return null;
            return temp;
        }
    

Log in to reply
 

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