首页 > 试题广场 >

恢复二叉搜索树

[编程题]恢复二叉搜索树
  • 热度指数：14252 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
二叉搜索树（BST）中的两个节点的值被错误地交换了，
请在不改变树的结构的情况下恢复这棵树。
备注；
用O(n)的空间解决这个问题的方法太暴力了，你能设计一个常数级空间复杂度的算法么？

示例 1:

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

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



说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
开通博客
头像 卑微大橙子在线求offer
发表于 2020-05-29 21:27:51
传送门 题目 二叉搜索树（BST）中的两个节点被错误地交换了，需要在不改变树的结构的情况下恢复这棵树。 思路 一开始理解错了，以为是两个同一层的节点被交换了，后来发现是我想简单了，题意指的是任意的两个节点；那么如何找到这两个节点呢？ 由二叉搜索树的概念，我们知道左子树所有节点的值都小于根节点的值，右 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-23 00:25:05
二叉搜索树的中序遍历是有序的，如果二叉搜索树中两个节点被互换了，那么其中序遍历中必定有两个节点“错位”，因此中序遍历是解题的关键。中序遍历本身不难，但是题目要求常数级别的空间复杂度，因此想到了线索二叉树。 总结下来两种思路: 空间复杂度为O(n)——线索二叉树 空间复杂度为O(logn)——递归， 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 一叶浮尘
发表于 2020-04-11 13:45:46
树练习的最后一道题目，说实话看的不是很懂，也没有太多的思路
去ta的博客 赞 (1) 回复(0) 收起
头像 O-Precedence
发表于 2021-09-09 16:29:20
class Solution { private TreeNode t1,t2,pre; public void recoverTree(TreeNode root) { inOrder(root); int temp = t1.val; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客487629784号
发表于 2022-01-27 18:45:08
* Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

树
难度：
70条回答 23644浏览

热门推荐

通过挑战的用户

查看代码

相关试题

恢复二叉搜索树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号