LeetCode #897递增顺序搜索树解法遇TreeNode循环错误求助

错误根源：未清理原节点的旧指针导致循环引用 #

你的代码中序遍历逻辑是正确的，但在拼接新树时，没有清空原节点的旧指针引用，导致出现循环：

针对测试用例[2,1,4,null,null,3]，原树结构中节点4的左子节点是3。中序遍历后队列中的节点顺序为1、2、3、4：

• 拼接时，你将3的右指针设为4，但节点4的左指针仍然指向3
• 此时3.right = 4且4.left = 3，形成了循环引用，触发LeetCode的循环检测报错

修复方案 #

在拼接新树的环节，取出队列中的节点后，先清空它的左、右指针，再将其连接到当前节点的右侧：

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();
        // 清空根节点的旧指针
        newRoot.left = null;
        newRoot.right = null;
        current = newRoot;
        while(!q.isEmpty()){
            TreeNode nextNode = q.remove();
            // 清空当前节点的旧指针，避免循环
            nextNode.left = null;
            nextNode.right = null;
            current.right = nextNode;
            current = current.right;
        }
        
        return newRoot;
    }
}

补充说明 #

原代码只清空了当前节点的左指针，但未处理新节点的旧指针。通过在拼接前清空每个节点的左右指针，彻底切断了原树中的旧引用关系，避免循环产生。

内容的提问来源于stack exchange，提问作者Jeff