【Leetcode】Recover Binary Search Tree
发布时间：2020-12-13 21:06:37 所属栏目：PHP教程 来源：网络整理
导读：题目链接：https://leetcode.com/problems/recover-binary-search-tree/ 题目： Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O( n ) space is pretty st
|
题目链接：https://leetcode.com/problems/recover-binary-search-tree/ 题目： Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
思路： 1.中序 保存所有结点 空间复杂度O(n)
2.中序递归 保存前1个结点的指针 找到不对的结点 算法：
public void recoverTree(TreeNode root) {
inorder(root);
if (third != null) {// 2次逆序
int tmp = first.val;
first.val = third.val;
third.val = tmp;
} else {// 1次逆序
int tmp = second.val;
second.val = first.val;
first.val = tmp;
}
}
TreeNode pre,first,second,third;
public void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
if (pre == null) {
pre = root;
} else {
if (root.val < pre.val) {
if (first == null) { // 如果第1次逆序 需要交换first和second结点
first = pre;
second = root;
} else {// 如果第2次逆序 只需要交换first和third结点
third = root;
}
}
}
pre = root;
inorder(root.right);
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |