「这是我参与11月更文挑战的第18天,活动详情查看:2021最后一次更文挑战」
前言
力扣第九十九题 恢复二叉搜索树
如下所示:
给你二叉搜索树的根节点 root
,该树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。
进阶: 使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗?
示例 1:
输入: root = [1,3,null,null,2]
输出: [3,1,null,null,2]
解释: 3 不能是 1 左孩子,因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
复制代码
一、思路
题目中有一个重要的信息:树中有两个节点被错误的交换。那么我们只需要找到这两个节点,再将他两交换,就能获得一个正确的二叉搜索树。
那怎么样才能找到这两个错误交换的节点呢?
我们知道有效 二叉搜索树定义如下:
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
我们发现 左子树的值是小于当前节点的值
且 右子树的值是大于当前节点的值
。我们可以使用 中序遍历(左根右)
来遍历这个树,我们可以得到一个数组。我们再在这个数组中找到需要交换的两个节点,最后再将这两个节点的值交换即可。
举个例子
我们以下图的树 [3, 1, 4, null, null, 2]
作为例子:
中序遍历后,得到的数组为 [1, 3, 2, 4]
数组中交换的位置为:第一次下降的位置和第一次上升的位置。(如果将递增数组看作一个斜向上的直线, 只有交换凸起处和下凹处的值,才能重新得到一条斜向上的直线)
很明显我们应该交换 2
和 3
的位置,交换后数组为 [1, 2, 3, 4]
,树如下图所示:
为了避免第二次遍历数组,我们可以在遍历树的时候就生成一个数组。只需要判断当前值与前一个值的大小即可,如果当前值小于数组最后的一个值我们就记录这个节点。
二、实现
实现代码
实现代码与思路中保持一致,数组我们这里替换为 栈
来保存节点
TreeNode x=null, y=null; // 下标
public void recoverTree(TreeNode root) {
dfs(root, new LinkedList<>());
// 交换x,y的值(两种情况)
int temp = x.val;
x.val = y.val;
y.val = temp;
}
public void dfs(TreeNode node, Deque<TreeNode> stack) {
if (node == null) {
return;
}
dfs(node.left, stack);
if (!stack.isEmpty() && node.val < stack.peek().val) {
if (x == null) {
x = stack.peek();
}
y = node;
}
stack.push(node);
dfs(node.right, stack);
}
复制代码
测试代码
public static void main(String[] args) {
TreeNode treeNode = new TreeNode(1, new TreeNode(3, null, new TreeNode(2)), null);
new Number99().recoverTree(treeNode);
}
复制代码
结果
三、总结
感谢看到最后,非常荣幸能够帮助到你~♥
如果你觉得我写的还不错的话,不妨给我点个赞吧!如有疑问,也可评论区见~
近期评论