LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】

本文主要是介绍LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入格式

root：二叉树的根节点。

输出格式

不需要返回值，直接在原树上进行恢复。

示例

示例 1

输入: [1,3,null,null,2]
输出: [3,1,null,null,2]
解释: 3 和 1 被错误交换。

示例 2

输入: [3,1,4,null,null,2]
输出: [2,1,4,null,null,3]
解释: 2 和 3 被错误交换。

方法一：中序遍历和交换

解题步骤

中序遍历：使用中序遍历找到两个错误的节点。
节点交换：找到两个不符合中序递增顺序的节点后，交换它们的值。

完整的规范代码

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef recoverTree(root):"""使用中序遍历恢复二叉搜索树:param root: TreeNode, 二叉搜索树的根节点"""stack = []x = y = prev = Nonewhile stack or root:while root:stack.append(root)root = root.leftroot = stack.pop()if prev and root.val < prev.val:y = rootif not x:x = prevelse:breakprev = rootroot = root.right# 交换两个节点的值if x and y:x.val, y.val = y.val, x.val# 示例调用
root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
recoverTree(root)

算法分析

时间复杂度：(O(n))，需要遍历所有节点。
空间复杂度：(O(h))，其中 (h) 是树的高度，用于存储栈。

中序遍历的 ASCII 图解

假设我们有一个二叉树，其中两个节点值被错误交换，例如树结构为：

    3/ \1   4/2

中序遍历应为 [1, 3, 4, 2]，但正确的排序应为 [1, 2, 3, 4]，其中 4 和 2 被错误地交换。

开始中序遍历：访问节点 3|   去左 -> 访问节点 1|   |   打印节点 1|   |   返回节点 3|   打印节点 3|   去右 -> 访问节点 4|   |   去左 -> 访问节点 2|   |   |   打印节点 2|   |   |   返回节点 4|   |   打印节点 4|   |   结束

方法二：Morris 中序遍历

解题步骤

Morris 遍历：这种遍历方式不需要额外的空间，通过修改树的结构实现。
找出并交换错误节点：在遍历过程中寻找顺序错误的节点，并在遍历结束后交换它们的值。

完整的规范代码

def recoverTree(root):x = y = prev = pred = Nonewhile root:if root.left:pred = root.leftwhile pred.right and pred.right != root:pred = pred.rightif not pred.right:pred.right = rootroot = root.leftelse:if prev and root.val < prev.val:y = rootif not x:x = prevprev = rootpred.right = Noneroot = root.rightelse:if prev and root.val < prev.val:y = rootif not x:x = prevprev = rootroot = root.rightif x and y:x.val, y.val = y.val, x.val# 示例调用
root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
recoverTree(root)

算法分析

时间复杂度：(O(n))，虽然是 Morris 遍历，每个节点最多被访问两次。
空间复杂度：(O(1))，不使用额外空间，除非修改了树的结构。

不同算法的优劣势对比

特征	方法一：中序遍历	方法二：Morris 遍历
时间复杂度	(O(n))	(O(n))
空间复杂度	(O(h))	(O(1))
优势	易于理解和实现	不需要额外空间
劣势	空间复杂度较高	修改了树的结构

Morris 遍历的 ASCII 图解

使用同样的树结构进行 Morris 遍历，我们通过修改树的结构来避免使用额外的空间。

开始Morris遍历：访问节点 3|   左节点存在，找到前驱（节点 1）|   |   前驱的右节点为空，链接到当前节点|   |   去左|   访问节点 1|   |   前驱是节点 3，断开链接，打印节点 1|   |   返回节点 3，打印节点 3|   去右 -> 访问节点 4|   |   左节点存在，找到前驱（节点 2）|   |   |   前驱的右节点为空，链接到当前节点|   |   |   去左|   |   访问节点 2|   |   |   前驱是节点 4，断开链接，打印节点 2|   |   |   返回节点 4，打印节点 4|   |   结束