一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 513|回复: 2
收起左侧

[Leetcode] Recover BST...直接对调一下节点的值真的可以吗

[复制链接] |试试Instant~ |关注本帖
金妮韦崽 发表于 2014-8-22 11:20:15 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

感觉一般情况下,能不直接给二叉树/链表改值的,都不会直接改值
这道题要求用O(1)空间复杂度,然后我只能想到找到两个对调节点以后改值了。看了一下我一直参考的“正确答案”也是这么写的= =
这算不算是偷懒啊。。。面试官会问如果不改值怎么做吗

我代码这么写的:
  1. public class Solution {
  2.    
  3.     private TreeNode current = null;
  4.     private TreeNode mistaken1 = null;
  5.     private TreeNode mistaken2;
  6.    
  7.     public void recoverTree(TreeNode root) {
  8.         traverse(root);
  9.         int temp = mistaken1.val;
  10.         mistaken1.val = mistaken2.val;
  11.         mistaken2.val = temp;
  12.     }
  13.    
  14.     public void traverse(TreeNode root) {
  15.         if (root != null) {
  16.             traverse(root.left);
  17.             if (current != null && root.val < current.val) {
  18.                 if (mistaken1 == null) {
  19.                     mistaken1 = current;
  20.                 }
  21.                 if (mistaken1 != null) {
  22.                     mistaken2 = root;
  23.                 }
  24.             }
  25.             current = root;
  26.             traverse(root.right);
  27.         }
  28.     }
  29. }
复制代码
eaglesky1990 发表于 2014-8-22 17:51:20 | 显示全部楼层
我觉得除了直接改值没别的办法了吧。。如果这不允许,还原二叉树就只能修改结构了。

另外,我看网上很多答案都用了递归。递归调用是会用到递归栈的,空间复杂度是O(n), 我觉得不合题目要求。
回复 支持 反对

使用道具 举报

wzf1943 发表于 2014-8-25 00:57:16 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 17:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表