【数据机构与算法】之深入解析“恢复二叉搜索树”的求解思路与算法示例

举报
Serendipity·y 发表于 2022/02/17 01:11:17 2022/02/17
【摘要】 一、题目要求 给你二叉搜索树的根节点 root ,该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树。示例 1: 输入:root = [1,3,null,null,2] 输...

一、题目要求

  • 给你二叉搜索树的根节点 root ,该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下,恢复这棵树。
  • 示例 1:

在这里插入图片描述

输入:root = [1,3,null,null,2]
输出:[3,1,null,null,2]
解释:3 不能是 1 的左孩子,因为 3 > 1 。交换 13 使二叉搜索树有效。

  
 
  • 1
  • 2
  • 3
  • 示例 2:

在这里插入图片描述

输入:root = [3,1,4,null,null,2]
输出:[2,1,4,null,null,3]
解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 23 使二叉搜索树有效。

  
 
  • 1
  • 2
  • 3
  • 提示:
    • 树上节点的数目在范围 [2, 1000] 内;
    • -231 <= Node.val <= 231 - 1。

二、求解算法

① 扫描遍历

  • 由于是二叉搜索树,这就是意味着节点之间是有顺序关系的,如果把整棵树都遍历一遍,将遍历的结果保存下来,比如放到一个数组中,那么这个数组应该是有序的。
  • 既然是有序的那就很好处理了,我们将这个有序的数组遍历一遍,如果数组是完全有序的,那么直接返回就可以了;否则,找到顺序不一致的两个下标 i 和 j,将 arr[i].val 和 arr[j].val 的值互换一下即可。

在这里插入图片描述

  • Java 示例:
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);
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 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

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

② 中序遍历

  • 解法①中,利用了额外的数组保存了遍历的结果,如果后面一个数比前面一个数小,那就找到了要交换的节点。

在这里插入图片描述

  • 按照同样的思路,用中序遍历的方式遍历这颗二叉搜索树,再增加一个辅助的 pre 指针,记录上一个节点的值。如果当前节点的值,小于上一个节点的值,这就找到了需要交换的节点。利用这种方式,就不需要额外的数组空间了。
  • 整个过程如下所示:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

  • 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);
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 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

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

③ 莫里斯遍历

  • 解法②还不是真正的常数空间复杂度,想要达到常数空间,可以用“莫里斯遍历”,这种方式可以做到 O(1) 的空间复杂度去遍历一棵树。
  • 回想一下中序遍历的递归版本,也就是一路往左走到底,左边走不通,再往右边走:
dfs(root.left)
打印节点 root
dfs(root.right)

  
 
  • 1
  • 2
  • 3
  • 如下所示,就是 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,将这个指向关系还原即可。从上图中也可以看出,所谓新加的指向关系,就是找到根节点左子树的最右子树,然后将最右子树的 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;
		}
	}
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 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
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

文章来源: blog.csdn.net,作者:Serendipity·y,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/Forever_wj/article/details/122963015

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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