Medium

题目描述

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

  • 树上节点的数目在范围 [2, 1000] 内
  • -2³¹ <= Node.val <= 2³¹ - 1

进阶： 使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

解题思路

解题思路

核心观察： 在正确的二叉搜索树中，中序遍历的结果是严格递增的。如果有两个节点被错误交换，那么在中序遍历中会出现逆序对。

分析交换情况：

  1. 相邻节点交换： 中序遍历中只会出现一个逆序对，如 [1,3,2,4] 中的 (3,2)
  2. 非相邻节点交换： 中序遍历中会出现两个逆序对，如 [1,4,3,2,5] 中的 (4,3) 和 (3,2)

解法一：中序遍历 + 数组存储（O(n)空间）

  • 先进行中序遍历，将所有节点按顺序存入数组
  • 在数组中找到被交换的两个节点
  • 交换这两个节点的值

解法二：Morris中序遍历（O(1)空间）【推荐】

  • 使用Morris遍历实现O(1)空间的中序遍历
  • 在遍历过程中实时检测逆序对
  • 记录需要交换的两个节点，最后交换它们的值

Morris遍历通过利用叶子节点的空指针来建立临时连接，实现了不使用栈或递归的树遍历。

代码实现

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode* first = nullptr;
        TreeNode* second = nullptr;
        TreeNode* prev = nullptr;
        
        TreeNode* current = root;
        
        while (current) {
            if (!current->left) {
                // 访问当前节点
                if (prev && prev->val > current->val) {
                    if (!first) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current->right;
            } else {
                // 找到前驱节点
                TreeNode* predecessor = current->left;
                while (predecessor->right && predecessor->right != current) {
                    predecessor = predecessor->right;
                }
                
                if (!predecessor->right) {
                    // 建立连接
                    predecessor->right = current;
                    current = current->left;
                } else {
                    // 恢复连接，访问当前节点
                    predecessor->right = nullptr;
                    if (prev && prev->val > current->val) {
                        if (!first) {
                            first = prev;
                            second = current;
                        } else {
                            second = current;
                        }
                    }
                    prev = current;
                    current = current->right;
                }
            }
        }
        
        // 交换两个节点的值
        if (first && second) {
            swap(first->val, second->val);
        }
    }
};

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        first = second = prev = None
        current = root
        
        while current:
            if not current.left:
                # 访问当前节点
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
            else:
                # 找到前驱节点
                predecessor = current.left
                while predecessor.right and predecessor.right != current:
                    predecessor = predecessor.right
                
                if not predecessor.right:
                    # 建立连接
                    predecessor.right = current
                    current = current.left
                else:
                    # 恢复连接，访问当前节点
                    predecessor.right = None
                    if prev and prev.val > current.val:
                        if not first:
                            first = prev
                            second = current
                        else:
                            second = current
                    prev = current
                    current = current.right
        
        # 交换两个节点的值
        if first and second:
            first.val, second.val = second.val, first.val

public class Solution {
    public void RecoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null;
        TreeNode current = root;
        
        while (current != null) {
            if (current.left == null) {
                // 访问当前节点
                if (prev != null && prev.val > current.val) {
                    if (first == null) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current.right;
            } else {
                // 找到前驱节点
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    // 建立连接
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // 恢复连接，访问当前节点
                    predecessor.right = null;
                    if (prev != null && prev.val > current.val) {
                        if (first == null) {
                            first = prev;
                            second = current;
                        } else {
                            second = current;
                        }
                    }
                    prev = current;
                    current = current.right;
                }
            }
        }
        
        // 交换两个节点的值
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }
}

var recoverTree = function(root) {
    let first = null, second = null, prev = null;
    let current = root;
    
    while (current) {
        if (!current.left) {
            // 访问当前节点
            if (prev && prev.val > current.val) {
                if (!first) {
                    first = prev;
                    second = current;
                } else {
                    second = current;
                }
            }
            prev = current;
            current = current.right;
        } else {
            // 找到前驱节点
            let predecessor = current.left;
            while (predecessor.right && predecessor.right !== current) {
                predecessor = predecessor.right;
            }
            
            if (!predecessor.right) {
                // 建立连接
                predecessor.right = current;
                current = current.left;
            } else {
                // 恢复连接，访问当前节点
                predecessor.right = null;
                if (prev && prev.val > current.val) {
                    if (!first) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current.right;
            }
        }
    }
    
    // 交换两个节点的值
    if (first && second) {
        [first.val, second.val] = [second.val, first.val];
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
Morris中序遍历O(n)O(1)
普通中序遍历O(n)O(n)

说明：

  • 时间复杂度： O(n)，需要遍历所有节点一次，Morris遍历虽然看起来有嵌套循环，但每条边最多被访问两次
  • 空间复杂度： O(1)，Morris遍历只使用常数级别的额外空间，不需要递归栈或额外数组