算法

每日leetcode-99

  1. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

其实就相当于说全部排好序后，看第一个比右边大的和最后一个比左边小的，交换一下。

如果直接把它们全都放到数组里面，扫描一遍就行。这里是在遍历的时候进行操作。

要注意stack的pop是没有返回值的！

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        // find the first > right and last < left
        // mid order
        stack<TreeNode*> t;
        TreeNode* now = root;
        TreeNode *last = NULL;
        TreeNode *first;
        bool found_first = false;
        TreeNode *last_ill_smaller_than_left;
        while (now || !t.empty()) {
            if (!now) {
                now = t.top();
                t.pop();
                // visit now
                if (last && last->val > now->val) {
                    last_ill_smaller_than_left = now;
                    if (!found_first) {
                        first = last;
                        found_first = true;
                    }
                }
                last = now;
                now = now->right;
            }
            else {
                t.push(now);
                // visit its left
                now = now->left;
            }
        }
        int temp = first->val;
        first->val = last_ill_smaller_than_left->val;
        last_ill_smaller_than_left->val = temp;
    }
};

空间消耗是O(树的高度)，也就是O(lgn)

O(1)空间复杂度的是一个叫做Morris 遍历的方法。

https://www.cnblogs.com/grandyang/p/4297300.html

A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.

就是说螺纹二叉树实际上是把所有原本为空的右子节点指向了中序遍历顺序之后的那个节点，把所有原本为空的左子节点都指向了中序遍历之前的那个节点，具体例子可以点击这里。那么这道题跟这个螺纹二叉树又有啥关系呢？由于我们既不能用递归，又不能用栈，那我们如何保证访问顺序是中序遍历的左-根-右呢。原来我们需要构建一个螺纹二叉树，需要将所有为空的右子节点指向中序遍历的下一个节点，这样中序遍历完左子结点后，就能顺利的回到其根节点继续遍历了。

  1. 初始化指针 cur 指向 root
  2. 当 cur 不为空时
    　 - 如果 cur 没有左子结点
    　 a) 打印出 cur 的值
    　　 b) 将 cur 指针指向其右子节点
    　 - 反之
    　 将 pre 指针指向 cur 的左子树中的最右子节点　
    　　　 * 若 pre 不存在右子节点
    　　　 a) 将其右子节点指回 cur
    　　　　 b) cur 指向其左子节点
    　　　 * 反之
    　　　　　 a) 将 pre 的右子节点置空
    　　　　　 b) 打印 cur 的值
    　　　　　 c) 将 cur 指针指向其右子节点
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
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *cur = root, *pre = nullptr ;
        while (cur) {
            if (cur->left){
                TreeNode *p = cur->left;
                while (p->right && p->right != cur) p = p->right;  // 左子树的最右节点
                if (!p->right) {
                    p->right = cur;
                    cur = cur->left;
                    continue;
                } else {  // 【1】else的时候是p->right == cur
                    p->right = NULL;
                }  
            }
            if (pre && cur->val < pre->val){
              if (!first) first = pre;
              second = cur;
            }
            pre = cur;
            cur = cur->right;  // 所以后续会到【1】的位置，走到【1】的else里面
        }
        swap(first->val, second->val);
    }
};