题解：538.把二叉搜索树转换为累加树
原文中文，约1200字，阅读约需3分钟。
📝
内容提要
将二叉搜索树转换为累加树，使每个节点的新值等于原树中大于或等于该节点值的和。通过反向中根遍历（右中左）实现，采用Morris遍历方法，时间复杂度为O(n)，空间复杂度为O(1)。
🔎
延伸解读
反向中序遍历的直观理解
二叉搜索树的中序遍历（左-中-右）得到升序序列，而题目要求每个节点的新值为原树中大于等于该节点值的和。因此，采用反向中序遍历（右-中-左）得到降序序列，在遍历过程中累加节点值，即可自然满足要求。这种思路将问题转化为对降序序列的累加，避免了额外的排序或查找操作。
Morris遍历的空间优势
常规的中序遍历使用栈或递归，空间复杂度为O(n)。Morris遍历利用树中空闲的指针（叶子节点的左右空指针）来临时存储前驱或后继信息，从而在遍历过程中无需额外空间。本题代码通过修改右子树最左节点的左指针来建立临时连接，遍历完成后恢复原树结构，实现了O(1)的空间复杂度。
实现细节与注意事项
在反向Morris遍历中，需要寻找当前节点右子树的最左节点，并利用其左指针建立临时链接。第一次访问时，将最左节点的左指针指向当前节点，并向右移动；第二次访问时，断开链接并处理当前节点。代码中通过判断mostLeft.left是否为空或等于cur来区分两次访问。注意在累加和更新后，需向左移动继续遍历。
❓
Q&A
如何将二叉搜索树转换为累加树？
通过反向中根遍历（右中左）来实现，使每个节点的新值等于原树中大于或等于该节点值的和。
二叉搜索树的特点是什么？
二叉搜索树的左子树节点值小于节点值，右子树节点值大于节点值，且左右子树也必须是二叉搜索树。
使用Morris遍历的优点是什么？
Morris遍历的时间复杂度为O(n)，空间复杂度为O(1)，因此非常高效。
反向中根遍历的目的是什么？
反向中根遍历用于获取降序序列，从而实现节点值的累加。
如何实现节点值的累加？
在反向中根遍历过程中，累计求和并更新当前节点的值。
转换后的累加树有什么特点？
转换后的累加树中，每个节点的新值等于原树中大于或等于该节点值的和。
🏷️
