Leetcode #897: final test case not working for Increasing Order Search Tree-CodePudding

I have written a solution for Leetcode question number 897: Increasing Order Search Tree but the final test case gave a an error which said that it found a cycle in TreeNode. I hand traced the algorithm for that test case and looks fine in my eyes. Need help figuring out what it meant by "found cycle in TreeNode".

Question Description:

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

My solution passed for this test case: Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] Output/Expected: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

This is the test case which it didn't work for: Input: [2,1,4,null,null,3] Output: Error - Found cycle in the TreeNode

Expected Output: [1,null,2,null,3,null,4]

P.S. - i know this might not be the best/optimal solution but it's the one i came up with so I need to figure out why it doesn't work for a single test case.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode increasingBST(TreeNode root) {
        TreeNode current = root;
        TreeNode newRoot = null;
        Queue<TreeNode> q = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        

        
        while(true){
            if(current != null){
                stack.push(current);
                current = current.left;
            }
            
            if(stack.isEmpty()){
                break;
            }
            
            if(current == null){
                current = stack.pop();
                q.add(current);
                
                current = current.right;
            }
        }
        
        newRoot = q.remove();
        current = newRoot;
        while(!q.isEmpty()){
            current.right = q.remove();
            current.left = null;
            current = current.right;
        }
        
        return newRoot;
        
        
    }
}

CodePudding user response：

Your queue contains [1,2,3,4] at the time of dequeuing.

        while(!q.isEmpty()){
            current.right = q.remove();
            current.left = null;
            current = current.right;
        }

The block never processes 4 as current, since 3 is the last node with a right child. As such, you're never resetting 4's children to null, and the right child still points to 3 from the original tree.

This simple check would reset the children for the last node:

        while(!q.isEmpty()){
            current.right = q.remove();
            current.left = null;
            current = current.right;
        }
        current.right = null;
        current.left = null;