What's wrong with my code or my thought?


  • 0
    L

    I use BFS to add every node to a new linkedlist at that level, so each next pointer point to its next right node, and last node's next pointer point to null.

    public class Solution {
    public void connect(TreeLinkNode root) {
        LinkedList<TreeLinkNode> cur = new LinkedList<TreeLinkNode>();
        if (root != null) cur.add(root);
        
        while (cur.size() > 0) {
            LinkedList<TreeLinkNode> parents = cur;
            cur = new LinkedList<TreeLinkNode>();
            for (TreeLinkNode tr : parents) {
                if (tr.left != null) cur.add(tr.left);
                if (tr.right != null) cur.add(tr.right);
            }
        }
    }
    

    }

    Submission Result: Wrong Answer

    Input: {1,2,3}
    Output: {1,#,2,#}
    Expected: {1,#,2,3,#}

    I add a for loop to put [i].next = [i + 1] in each list, it passes all the test cases and is accepted.

    public class Solution {
    public void connect(TreeLinkNode root) {
        LinkedList<TreeLinkNode> cur = new LinkedList<TreeLinkNode>();
        if (root != null) cur.add(root);
        
        while (cur.size() > 0) {
            LinkedList<TreeLinkNode> parents = cur;
            cur = new LinkedList<TreeLinkNode>();
            for (TreeLinkNode tr : parents) {
                if (tr.left != null) {
                    cur.add(tr.left);
                    cur.add(tr.right);
                }
            }
                if (!cur.isEmpty()) {
                for (int i = 0; i < cur.size() - 1; i++) {
                    cur.get(i).next = cur.get(i + 1);
                }
                cur.getLast().next = null;
            }
        }
    }
    

    }

    ACCEPTED!


  • 0
    M

    The way this problem is judged, based on the expected answer and how your output is formatted, is to take the leftmost element and travel through the next pointers until it reaches a null. While your algorithm does put all the nodes into a list, with the elements ordered from left to right, you aren't ever setting the next property in TreeLinkNode.

    If you want an easy way to solve this problem from where you are, after the for loop, iterate through the contents of the linked list putting [i].next = [i+1] for all but the last element. This may cause a time limit exceeded, but you should also be able to adapt that into a faster method.


  • 0
    L

    Yes you are right, but I add a for loop to put [i].next = [i+1], it is incredible accepted!!


Log in to reply
 

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