我的Morris遍历代码问题排查：恢复BST时触发空指针异常

核心问题分析 #

报错指向第56行arr.add(a.val);的NullPointerException，说明a或b为null。根源有两个：

1. 前驱节点查找逻辑错误：rmt函数仅执行一次节点移动，未循环找到左子树的最右节点（真正的前驱节点），导致Morris遍历流程混乱，无法正确检测到逆序对，最终a、b未被赋值。
2. 未处理树本身合法的边界情况：若输入BST原本就是有序的，a、b会保持null，直接访问val会触发空指针。

修复步骤 #

1. 修正前驱节点查找函数 #

将rmt函数的单次判断改为循环，确保找到左子树的最右节点：

public TreeNode rmt(TreeNode leftNode, TreeNode currNode){
    // 循环找到左子树的最右节点（前驱）
    while(leftNode.right != null && leftNode.right != currNode){
        leftNode = leftNode.right;
    }
    return leftNode;
}

2. 增加空指针防护 #

在最后赋值前，判断a和b是否为null（应对树本身合法的场景）：

ArrayList<Integer> arr = new ArrayList<>();
// 若树本身有序，按需求处理，这里假设题目保证存在逆序对
if(a != null && b != null){
    arr.add(a.val);
    arr.add(b.val);
}
return arr;

完整修复后的代码 #

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    public TreeNode rmt(TreeNode leftNode, TreeNode currNode){
        while(leftNode.right != null && leftNode.right != currNode){
            leftNode = leftNode.right;
        }
        return leftNode;
    }
    
    public ArrayList<Integer> recoverTree(TreeNode A) {
        TreeNode currNode = A;
        TreeNode a=null;
        TreeNode b=null;
        TreeNode prevNode=null;
        
        while(currNode!=null){
            TreeNode leftNode = currNode.left;
            if(leftNode==null){
                // 无左子树，直接访问当前节点
                if(prevNode!=null && prevNode.val>currNode.val){
                    if(a==null){
                        a=prevNode;
                    }
                    b=currNode;
                }
                prevNode=currNode;
                currNode=currNode.right;
            }else{
                TreeNode rightNode = rmt(leftNode,currNode);
                if(rightNode.right==null){
                    // 建立前驱节点到当前节点的链接
                    rightNode.right=currNode;
                    currNode=currNode.left;
                }else{
                    // 已访问左子树，断开链接并访问当前节点
                    rightNode.right=null;
                    if(prevNode!=null && prevNode.val>currNode.val){
                        if(a==null){
                            a=prevNode;
                        }
                        b=currNode;
                    }
                    prevNode=currNode;
                    currNode=currNode.right;
                }
            }
        }
        
        ArrayList<Integer> arr = new ArrayList<>();
        if(a != null && b != null){
            arr.add(a.val);
            arr.add(b.val);
        }
        return arr;
    }
}

验证说明 #

修正后的rmt函数能正确找到前驱节点，保证Morris遍历按中序顺序访问所有节点，从而准确检测到交换的两个节点。空指针防护则避免了树本身有序时的异常。

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