恢复二叉搜索树(LeetCode--99恢复二叉搜索树)
题目
二叉搜索树中的两个节点被错误地交换。在不改变其结构的情况下,恢复这棵树。
文章图片
摘自LeetCode99 解题方法
这道题在LeetCode中难度被定义为困难,主要是因为两方面:
- 第一如何找到错误交换的节点;
- 第二则是确定交换哪两个节点之后树可以恢复。
那么是哪两个节点错误了呢?这里<3,2><2,1><3,1>都是错误的数字对,题目中已知只有两个节点错误地被交换,选择间距最大的一组数字对,即<3,1>,交换<3,1>两个节点即是正确结果。
另外,因为只需要记录逆序的数字对,实际上不用记录全部的中序遍历结果,只需要常数空间复杂度即可,记录间距最大的一组逆序数字对。
代码 【恢复二叉搜索树(LeetCode--99恢复二叉搜索树)】在代码中进行详细注释
public void recoverTree(TreeNode root) {
//初始化两个空间的数组用于记录错误交换的树节点
TreeNode[] nodes = new TreeNode[]{null, null};
//调用中序遍历方法找到错误交换的节点
inorder(root, nodes);
//交换两个节点
if(nodes[1] != null){
int tmp = nodes[0].val;
nodes[0].val = nodes[1].val;
nodes[1].val = tmp;
}
}private void inorder(TreeNode root, TreeNode[] nodes){
if(null == root){
return;
}
Stack stack = new Stack<>();
while(root != null){
while(root != null){
stack.push(root);
root = root.left;
}
while(!stack.empty() && root== null){
root = stack.pop();
//遍历到节点时,观察nodes[0]为null,则是第一个节点
if(nodes[0] == null){
nodes[0] = root;
}else{
//中序遍历逆序的一个数据对,因为只有两个节点错误,不一定是相邻的两个数字,可能是隔开的。
//应该是间距最大的逆序数字对。
if(nodes[0].val < root.val && null == nodes[1]){
//升序节点,nodes[1]为null则尚有节点没有遍历,nodes[0]记录逆序对的可能起始节点
nodes[0] = root;
} else if(nodes[0].val < root.val && null != nodes[1]){
//如果升序节点,nodes[1]不为null,因为只有两个节点错误交换位置,则找到错误节点,停止程序
return;
} else {
//找到逆序数字对,nodes[1]记录逆序对的结束节点
nodes[1] = root;
}
}
root = root.right;
}
}
}
推荐阅读
- 【译】20个更有效地使用谷歌搜索的技巧
- java中如何实现重建二叉树
- 4.4复盘,第93天
- 二叉树路径节点关键值和等于目标值(LeetCode--112&LeetCode--113)
- 15个从现实焦虑中恢复精神的方法!
- MySql数据库备份与恢复
- locate搜索
- springboot结合redis实现搜索栏热搜功能及文字过滤
- 茶事|茶事 | 单丛里的一泡奇葩
- 达梦数据库|DM8表空间备份恢复