b****g
发帖数: 192 | 1 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
c***s
发帖数: 192 | 2 想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal.
【在 b****g 的大作中提到】
: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。
|
b****g
发帖数: 192 | 3 O(N)空间难道不是首先要inorder遍历一遍吗？
【在 c***s 的大作中提到】
: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.
|
l*****a
发帖数: 14598 | 4 inorder traverse不用‘额外空间吗
【在 c***s 的大作中提到】
: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.
|
c***s
发帖数: 192 | 5 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。
【在 b****g 的大作中提到】
: O(N)空间难道不是首先要inorder遍历一遍吗？
|
l*****a
发帖数: 14598 | 6 inorder traverse不用‘额外空间吗
【在 c***s 的大作中提到】
: O(N)空间的时候就是先inorder一遍。
: 但按照相同的思路，并不需要在inorder的时候保存所有的节点。
: 所以空间可以变为O(1).
: 比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
: 但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
: 所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
: 就可以了。
: 所需要的空间就是需要一个额外的变量来保存上一个node。
|
c***s
发帖数: 192 | 7 你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。
【在 l*****a 的大作中提到】
: inorder traverse不用‘额外空间吗
|
l*****a
发帖数: 14598 | 8 how do u do in-order traverse？
【在 c***s 的大作中提到】
: 你不需要记录所有nodes的话就不需要额外空间啊。
: 只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。
|
c***s
发帖数: 192 | 9 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
}
【在 l*****a 的大作中提到】
: how do u do in-order traverse？
|
b****g
发帖数: 192 | 10 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？
【在 c***s 的大作中提到】
: 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
: 如果考虑的话那就是O(logN)的空间了。
: 下面是我用java 写的函数。
: swap[2]用来记录上一个访问的node。
: swap[0]和swap[1]保存错位的nodes。
: void find_node(TreeNode root, TreeNode[] swap) {
: if(root == null) return;
: find_node(root.left, swap);
: if(swap[2] != null && swap[2].val > root.val) {
: if(swap[0] == null) swap[0] = swap[2];
|
|
|
i******e
发帖数: 273 | 11 Node *p, *q;
中序遍历此bst两次， 第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
1) |
b****g
发帖数: 192 | 12 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。 |
c***s
发帖数: 192 | 13 想象一下用O(N)空间时是咋算的，
然后将扫描数组的操作转换成inorder traversal.
【在 b****g 的大作中提到】
: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。
|
b****g
发帖数: 192 | 14 O(N)空间难道不是首先要inorder遍历一遍吗？
【在 c***s 的大作中提到】
: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.
|
l*****a
发帖数: 14598 | 15 inorder traverse不用‘额外空间吗
【在 c***s 的大作中提到】
: 想象一下用O(N)空间时是咋算的，
: 然后将扫描数组的操作转换成inorder traversal.
|
c***s
发帖数: 192 | 16 O(N)空间的时候就是先inorder一遍。
但按照相同的思路，并不需要在inorder的时候保存所有的节点。
所以空间可以变为O(1).
比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
就可以了。
所需要的空间就是需要一个额外的变量来保存上一个node。
【在 b****g 的大作中提到】
: O(N)空间难道不是首先要inorder遍历一遍吗？
|
l*****a
发帖数: 14598 | 17 inorder traverse不用‘额外空间吗
【在 c***s 的大作中提到】
: O(N)空间的时候就是先inorder一遍。
: 但按照相同的思路，并不需要在inorder的时候保存所有的节点。
: 所以空间可以变为O(1).
: 比如：用O(N)空间的时候，你的node是存在数组里，然后scan一次这个数组，
: 但其实你scan这个数组的操作其实跟inorder traversal的顺序是一模一样的。
: 所以其实你不需要用一个数组来保存nodes，而是自己用inorder traversal scan一遍
: 就可以了。
: 所需要的空间就是需要一个额外的变量来保存上一个node。
|
c***s
发帖数: 192 | 18 你不需要记录所有nodes的话就不需要额外空间啊。
只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。
【在 l*****a 的大作中提到】
: inorder traverse不用‘额外空间吗
|
l*****a
发帖数: 14598 | 19 how do u do in-order traverse？
【在 c***s 的大作中提到】
: 你不需要记录所有nodes的话就不需要额外空间啊。
: 只有你要将inorder traversal的结果都记录下来时才需要O(N) 的空间。
|
c***s
发帖数: 192 | 20 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
如果考虑的话那就是O(logN)的空间了。
下面是我用java 写的函数。
swap[2]用来记录上一个访问的node。
swap[0]和swap[1]保存错位的nodes。
void find_node(TreeNode root, TreeNode[] swap) {
if(root == null) return;
find_node(root.left, swap);
if(swap[2] != null && swap[2].val > root.val) {
if(swap[0] == null) swap[0] = swap[2];
swap[1] = root;
}
swap[2] = root;
find_node(root.right, swap);
}
【在 l*****a 的大作中提到】
: how do u do in-order traverse？
|
|
|
b****g
发帖数: 192 | 21 其实楼上几位反复询问的就是这个inorder怎么travel，因为如果递归的话那占用空间
肯定就不是O（1）了，用栈的话也不是O（1）。你给的的答案也用了递归，那就不是O
（1）了吧？
【在 c***s 的大作中提到】
: 不考虑递归函数压栈的空间，inorder traverse不需要额外空间。
: 如果考虑的话那就是O(logN)的空间了。
: 下面是我用java 写的函数。
: swap[2]用来记录上一个访问的node。
: swap[0]和swap[1]保存错位的nodes。
: void find_node(TreeNode root, TreeNode[] swap) {
: if(root == null) return;
: find_node(root.left, swap);
: if(swap[2] != null && swap[2].val > root.val) {
: if(swap[0] == null) swap[0] = swap[2];
|
i******e
发帖数: 273 | 22 Node *p, *q;
中序遍历此bst两次， 第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
1) |
l****i
发帖数: 396 | 23 这个中序遍历怎么O（1）空间？ DFS要用到stack，循环也是啊，难道循环的不算？
O(
【在 i******e 的大作中提到】
: Node *p, *q;
: 中序遍历此bst两次， 第一次遍历找到一个比前驱节点小的节点记为p, 第二次遍历找
: 到第一个比p指向节点大的节点记为q, swap(p, q); 时间复杂度 O(n), 空间复杂度 O(
: 1)
|
B********t
发帖数: 147 | 24 贴一个, 如果递归不算extra space....
class Solution {
public:
void recoverTree(TreeNode *root, TreeNode *&pre, TreeNode *&big,
TreeNode *&small, bool &first)
{
if(root)
{
recoverTree(root->left, pre, big, small, first);
if(first && root->val < pre->val)
{
big = pre;
first = false;
}
if(root->val < pre->val)
small = root;
pre = root;
recoverTree(root->right, pre, big, small, first);
}
}
void recoverTree(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TreeNode *pre = new TreeNode(INT_MIN);
TreeNode *big, *small;
bool first = true;
recoverTree(root, pre, big, small, first);
int temp = big->val;
big->val = small->val;
small->val = temp;
}
};
【在 b****g 的大作中提到】
: Two elements of a binary search tree (BST) are swapped by mistake.
: Recover the tree without changing its structure.
: 看了leetcode的discuss，也没给出思路。而且貌似也改变树的结构了。
|
