Leetcode前序遍历问题中Address Sanitizer报错：Morris遍历异常

我在LeetCode的「二叉树前序遍历」问题中用C++实现Morris遍历，测试用例[3,2,1]（3为根节点，1是左子节点，2是右子节点）下运行失败。取消preorderTraversal方法里两行注释后代码能正常运行，但我觉得这两行是多余的，搞不懂为啥会引发错误。

原代码 #

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> vals;
    while (root != nullptr) {
        if (root->left == nullptr) {
            vals.push_back(root->val);
            root = root->right;
        } else {
            TreeNode* last = root->left;
            while (last->right != nullptr) last = last->right;
            last->right = root->right;
            //TreeNode* temp = root; NOT INCLUDING THIS CAUSES ERROR
            vals.push_back(root->val);
            root = root->left;       
            //temp->left = NULL;     NOT INCLUDING THIS CAUSES ERROR
        }
    }
    
    return vals;
}

运行时错误信息（翻译后） #

运行时错误信息：
==================================================================
==24==错误：AddressSanitizer：在地址0x6030000003d8处发生堆内存释放后使用，程序计数器pc=0x00000038f4f5，基址bp=0x7ffd36eee010，栈指针sp=0x7ffd36eee008
线程T0对地址0x6030000003d8执行了大小为8的读操作
    #4 0x7f4383a9e082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x6030000003d8位于24字节内存区域[0x6030000003d0,0x6030000003e8)内的第8字节处
该内存区域由线程T0在此处释放：
    #5 0x7f4383a9e082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
该内存区域此前由线程T0在此处分配：
    #4 0x7f4383a9e082  (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
错误地址周围的阴影字节：
  0x0c067fff8020: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
  0x0c067fff8030: fa fa fd fd fd fa fa fa fd fd fd fa fa fa fd fd
  0x0c067fff8040: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
  0x0c067fff8050: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
  0x0c067fff8060: fa fa fd fd fd fa fa fa fd fd fd fa fa fa 00 00
=>0x0c067fff8070: 00 fa fa fa fd fd fd fa fa fa fd[fd]fd fa fa fa
  0x0c067fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff80c0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
阴影字节说明（1个阴影字节代表8个应用字节）：
  可寻址:           00
  部分可寻址: 01 02 03 04 05 06 07 
  堆左红区:       fa
  已释放堆区域:       fd
  栈左红区:      f1
  栈中红区:       f2
  栈右红区:     f3
  栈返回后:      f5
  栈作用域后使用:   f8
  全局红区:          f9
  全局初始化顺序:       f6
  用户标记中毒:        f7
  容器溢出:      fc
  数组Cookie:            ac
  对象内红区:    bb
  ASan内部:           fe
  左alloca红区:     ca
  右alloca红区:    cb
  阴影间隙:              cc
==24==终止程序

问题原因与解决方案 #

这两行代码绝非多余，它们是解决循环引用导致重复释放内存问题的核心。

先看测试用例的树结构：

3
   / \
  1   2

当处理根节点3时，你找到左子树1的最右节点（就是1自己），把1的右指针指向3的右孩子2。随后将root移到1，但3的左指针仍指向1。

LeetCode的测试框架在你的函数返回后，会自动递归删除所有树节点。此时问题出现：删除3时，会递归删除它的左孩子1；而1的右指针指向2，删除1时又会递归删除2。但2已经被删除过一次，这就触发了AddressSanitizer检测到的堆内存释放后使用错误。

那两行代码的作用：

• TreeNode* temp = root; 保存当前节点（3）的指针
• temp->left = NULL; 切断当前节点与左子树的连接

这样测试框架释放内存时，3的左指针已经是nullptr，不会再递归删除1，避免了重复删除节点的情况，内存错误也就消失了。

修正后的完整代码 #

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> vals;
    while (root != nullptr) {
        if (root->left == nullptr) {
            vals.push_back(root->val);
            root = root->right;
        } else {
            TreeNode* last = root->left;
            while (last->right != nullptr) last = last->right;
            last->right = root->right;
            TreeNode* temp = root;
            vals.push_back(root->val);
            root = root->left;       
            temp->left = NULL;
        }
    }
    
    return vals;
}

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