leetcode 99.恢复二叉搜索树
题目描述
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下,恢复这棵树。
示例 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) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗?
解法一
注意题目给出的条件,是二叉搜索树,这就是意味着节点之间是有顺序关系的。
如果我们用中序遍历把整棵树遍历一遍,并将遍历的结果保存下来,比如放到一个数组中。
那么这个数组应该是有序的。
既然是有序的那就好办了,我们将这个有序的数组遍历一遍。
如果数组是完全有序的,那么直接返回就可以了。
否则,我们找到顺序不一致的两个下标i
和j
,将arr[i].val
和arr[j].val
的值互换一下即可。
java代码:
</pre> class Solution { public void recoverTree(TreeNode root) { List<TreeNode> list = new ArrayList<TreeNode>(); dfs(root,list); TreeNode x = null; TreeNode y = null; //扫面遍历的结果,找出可能存在错误交换的节点x和y for(int i=0;i<list.size()-1;++i) { if(list.get(i).val>list.get(i+1).val) { y = list.get(i+1); if(x==null) { x = list.get(i); } } } //如果x和y不为空,则交换这两个节点值,恢复二叉搜索树 if(x!=null && y!=null) { int tmp = x.val; x.val = y.val; y.val = tmp; } } //中序遍历二叉树,并将遍历的结果保存到list中 private void dfs(TreeNode node,List<TreeNode> list) { if(node==null) { return; } dfs(node.left,list); list.add(node); dfs(node.right,list); } }
python代码:
class Solution(object): def recoverTree(self, root): nodes = [] # 中序遍历二叉树,并将遍历的结果保存到list中 def dfs(root): if not root: return dfs(root.left) nodes.append(root) dfs(root.right) dfs(root) x = None y = None pre = nodes[0] # 扫面遍历的结果,找出可能存在错误交换的节点x和y for i in xrange(1,len(nodes)): if pre.val>nodes[i].val: y=nodes[i] if not x: x = pre pre = nodes[i] # 如果x和y不为空,则交换这两个节点值,恢复二叉搜索树 if x and y: x.val,y.val = y.val,x.val
解法二
解法一种,我们利用了额外的数组保存了遍历的结果,如果后面一个数比前面一个数小,那就找到了要交换的节点。
按照同样的思路,用中序遍历的方式遍历这颗二叉搜索树,我们再增加一个辅助的pre
指针,记录上一个节点的值。
如果当前节点的值,小于上一个节点的值,这就找到了需要交换的节点。利用这种方式,就不需要额外的数组空间了。
注意,这种方式仍然使用了外部空间,虽然我们只用了常数个变量,但是递归调用仍然是需要额外空间的,其空间复杂度是O(h),h为树的高度。
所以用递归的方式遍历,或者手动模拟栈的方式遍历,都没有达到真正的常数空间。
java代码:
class Solution { //用两个变量x,y来记录需要交换的节点 private TreeNode x = null; private TreeNode y = null; private TreeNode pre = null; public void recoverTree(TreeNode root) { dfs(root); //如果x和y都不为空,说明二叉搜索树出现错误的节点,将其交换 if(x!=null && y!=null) { int tmp = x.val; x.val = y.val; y.val = tmp; } } //中序遍历二叉树,并比较上一个节点(pre)和当前节点的值,如果pre的值大于当前节点值,则记录下这两个节点 private void dfs(TreeNode node) { if(node==null) { return; } dfs(node.left); if(pre==null) { pre = node; } else { if(pre.val>node.val) { y = node; if(x==null) { x = pre; } } pre = node; } dfs(node.right); } }
python代码:
class Solution(object): def recoverTree(self, root): # 用两个变量x,y来记录需要交换的节点 self.x = None self.y = None self.pre = None # 中序遍历二叉树,并比较上一个节点(pre)和当前节点的值,如果pre的值大于当前节点值,则记录下这两个节点 def dfs(root): if not root: return dfs(root.left) if not self.pre: self.pre = root else: if self.pre.val>root.val: self.y = root if not self.x: self.x = self.pre self.pre = root dfs(root.right) dfs(root) # 如果x和y都不为空,说明二叉搜索树出现错误的节点,将其交换 if self.x and self.y: self.x.val,self.y.val = self.y.val,self.x.val
解法三
解法二还不是真正的常数空间复杂度,想要达到常数空间,我们可以用莫里斯遍历,这种方式可以做到O(1)的空间复杂度去遍历一棵树。
我们先看看莫里斯遍历到底是咋回事
回想一下中序遍历的递归版本是
dfs(root.left)
打印节点 root
dfs(root.right)
也就是一路往左走到底,左边走不通了,再往右边走。对于上图来说,就是4
->3
->1
这个过程,一路往左,走不通了再往右,也就是遍历2
。
当然如果2
的右边还有节点那么还会继续遍历下去。
现在2
的右边已经是空了,对于递归来说操作系统自动出栈,然后会访问3
这个节点。
既然2
是叶子节点,左右子树都是空,我们可以利用这个空闲出来的信息,将2
的右子树指向3
,这样当2
遍历完后,再往右走,就会自动走到3
这个节点了。
同理,将3
的右子树指向4
,将6
的右子树指向7
。
这样的话,我们就可以省去额外的栈空间了。利用叶子节点的右子树这个特点,将其重新赋予指向关系 ,就是莫里斯遍历的核心了。
不过光是这样还不行,再回看上面那张图,其实已经不是一棵树了,而是变成图了。因为出现了循环。
所以,我们还需要将新加这个指向关系给去掉。
对于上图来说,假设我们已经遍历到4
这个节点了,那就意味着4
的左子树都遍历完了,对应的就是1
,2
,3
都遍历完了。
3.right=4
这个是我们新加上的,既然现在已经遍历到4
了,我们就可以将3.right=null
,将这个指向关系还原即可。
从上图中也可以看出,所谓新加的指向关系,就是找到根节点左子树的最右子树(这里就是3),然后将最右子树的right
指向根节点。
动画演示如下:
仔细看上图,3
->1
->2
,这几个节点会走两遍。
第一遍的时候,3
的左子树的最右节点是2
,于是将2.right
指向3
。
之后等1
,2
两个节点都遍历完后,当前节点走到了3
这里,又会触发一遍 根节点的左子树的最右节点这个循环查找逻辑,此时可以判断出最右的节点2.right
是等于root的,所以就将2.right
重新设置为空,即还原回去。
为方便查看细节,我把执行过程也拼接了一个长图:
java代码:
class Solution { public void recoverTree(TreeNode root) { if(root==null) { return; } TreeNode x = null; TreeNode y = null; TreeNode pre = null; TreeNode tmp = null; while(root!=null) { if(root.left!=null) { tmp = root.left; while(tmp.right!=null && tmp.right!=root) { tmp = tmp.right; } if(tmp.right==null) { tmp.right = root; root = root.left; } else { if(pre!=null && pre.val>root.val) { y = root; if(x==null) { x = pre; } } pre = root; tmp.right = null; root = root.right; } } else { if(pre!=null && pre.val>root.val) { y = root; if(x==null) { x = pre; } } pre = root; root = root.right; } } if(x!=null && y!=null) { int t = x.val; x.val = y.val; y.val = t; } } }
python代码:
class Solution(object): def recoverTree(self, root): x = None y = None pre = None tmp = None while root: if root.left: tmp = root.left while tmp.right and tmp.right!=root: tmp = tmp.right if tmp.right is None: tmp.right = root root = root.left else: if pre and pre.val>root.val: y = root if not x: x = pre pre = root tmp.right = None root = root.right else: if pre and pre.val>root.val: y = root if not x: x = pre pre = root root = root.right if x and y: x.val,y.val = y.val,x.val
(全文完)