leetcode_99. 恢复二叉搜索树

举报
悲恋花丶无心之人 发表于 2021/02/03 01:57:31 2021/02/03
【摘要】 目录 一、题目内容 二、解题思路 三、代码 一、题目内容 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1   /  3   \    2 ...

目录

一、题目内容

二、解题思路

三、代码


一、题目内容

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下,恢复这棵树。

示例 1:

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗?

二、解题思路

中序遍历二叉搜索树则可以得到一个递增的序列,因此如果在这个序列中出现了两个数字交换,则大的数一定换到了小的数的位置,因此之后大的数和大的数之后的数组成了一个降序对,因此第一个降序对中的大数就是那个被换的数,但是和哪个换的就不知道了,因此还需要往后找。

再看小的数,因为被换到了后面,因此这个小的数比它现在位置之前的那个数要小,因此可以得到第二个降序对,因而第二个降序对里小的数就是那个和已经确定的大的数交换的。

因此中序遍历完成后,把得到的大数和小数交换即可恢复二叉搜索树。

例如:

[1,2,3,4,5,6]

3和6交换:

[1,2,6,4,5,3]

第一个降序对:

[6,4]

第二个降序对:

[5,3]

3确实比4和5小,因此记录6这个大数,再找到3这个小数交换即可,不然不是递增的。

三、代码


  
  1. # Definition for a binary tree node.
  2. class TreeNode:
  3. def __init__(self, val=0, left=None, right=None):
  4. self.val = val
  5. self.left = left
  6. self.right = right
  7. def __repr__(self):
  8. return str(self.val)
  9. class Solution:
  10. def __init__(self):
  11. self.large = None
  12. self.small = None
  13. self.pre = None
  14. def recoverTree(self, root: TreeNode) -> None:
  15. """
  16. Do not return anything, modify root in-place instead.
  17. """
  18. self.inorder(root)
  19. temp = self.large.val
  20. self.large.val = self.small.val
  21. self.small.val = temp
  22. def inorder(self, root):
  23. if not root:
  24. return
  25. self.inorder(root.left)
  26. if self.pre is not None and self.pre.val > root.val:
  27. if self.large is None: # 找到了第一个大数
  28. self.large = self.pre
  29. self.small = root # 一直找小数
  30. self.pre = root
  31. self.inorder(root.right)
  32. if __name__ == '__main__':
  33. a = TreeNode(1)
  34. a.left = TreeNode(3)
  35. a.left.right = TreeNode(2)
  36. s = Solution()
  37. s.recoverTree(a)
  38. print(a)

文章来源: nickhuang1996.blog.csdn.net,作者:悲恋花丶无心之人,版权归原作者所有,如需转载,请联系作者。

原文链接:nickhuang1996.blog.csdn.net/article/details/108729119

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。