leetcode 99.恢复二叉搜索树

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) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗?

解法一

注意题目给出的条件,是二叉搜索树,这就是意味着节点之间是有顺序关系的。
如果我们用中序遍历把整棵树遍历一遍,并将遍历的结果保存下来,比如放到一个数组中。
那么这个数组应该是有序的。

既然是有序的那就好办了,我们将这个有序的数组遍历一遍。
如果数组是完全有序的,那么直接返回就可以了。
否则,我们找到顺序不一致的两个下标ij,将arr[i].valarr[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的左子树都遍历完了,对应的就是123都遍历完了。
3.right=4这个是我们新加上的,既然现在已经遍历到4了,我们就可以将3.right=null,将这个指向关系还原即可。
从上图中也可以看出,所谓新加的指向关系,就是找到根节点左子树的最右子树(这里就是3),然后将最右子树的right指向根节点。

动画演示如下:

仔细看上图,3->1->2,这几个节点会走两遍。
第一遍的时候,3的左子树的最右节点是2,于是将2.right指向3
之后等12两个节点都遍历完后,当前节点走到了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
                                                                                         

(全文完)

1 次阅读

发表评论

电子邮件地址不会被公开。