leetcode50天刷题计划第二季(day 8 —恢复二叉搜索树(17.30-18.40_国际知名观众的博客-爱代码爱编程
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
最近跟二叉搜索树杠上了、、
一、题目
恢复二叉搜索树
给你二叉搜索树的根节点 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] 内
-231 <= Node.val <= 231 - 1
进阶
使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗?
二、思路
首先,解题的关键在于二叉搜索树的性质:对二叉搜索树进行中序遍历,得到的值序列是递增有序的。
如果错误地交换了两个节点,等价于在这个值序列中交换了两个值,破坏了值序列的递增性。
因此,只需要在对二叉树进行遍历的时候,找到所有非递增的“问题结点”即可(即某结点的值小于其前结点,root.val<root.left)
如果只能找到一个问题结点,就把此结点与其前结点的值交换;如果找到两个问题结点,就把第一个问题结点前的值和第二个问题结点互换即可
时间复杂度:O(N),其中 N 为二叉搜索树的高度。Morris 遍历中每个节点会被访问两次,因此总时间复杂度为 O(2N)=O(N)O(2N)=O(N)。
空间复杂度:O(1)。
注意,遍历时,为了在递归中保留上一个结点的指针,指针必须设置为全局变量(或引用类型),否则无法保存,会造成回溯
三、代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
question_node=[] #问题结点列表
q1=[None] #保证全局可用,因为递归同步不了变量
#递归实现遍历
def traverse(root):#遍历中指向上一个节点的指针
if(root == None):
return
traverse(root.left) #遍历
if(q1[0] and q1[0].val > root.val):
question_node.append([q1[0],root])#有问题的前一个结点和有问题的结点
q1[0]=root #指针向后移动
traverse(root.right) #遍历
#遍历
traverse(root)
#交换问题结点的值
if(len(question_node) == 1):
question_node[0][0].val,question_node[0][1].val=question_node[0][1].val,question_node[0][0].val
else:
question_node[0][0].val,question_node[1][1].val=question_node[1][1].val,question_node[0][0].val