头像

acw_zhw


访客:947

离线:5小时前



acw_zhw
12小时前

先讲Morris遍历,再讲lc99

最优解Morris traversal O(n) time, O(1) space 进行inorder traversal

为什么要用这个算法?
已有的两个inorder traversal的方法
1. dfs O(n) time O(n) space 优点: 写起来最简单
2. 栈模拟 O(n) time O(h) space NOTE h是树的高度,最差是O(n), 优点: space上可能比dfs更好
而Morris在space上吊打前两个,但是本质是时间换空间,因为每个点可能被遍历2遍才能确定顺序

想法

  1. inorder的顺序为左中右,所以(代码中的curr)的顺序要被确定分别有两种情况
    1) 遍历到为空
    2) 遍历到不为空,但是的所有节点已经被确定过顺序了 @ 需要一种机制去检验被确定下来了
  2. 这个机制就是当被完全确定后,的最后/最大一个节点能够回溯(通过它的->right)到 @ 这就是Morris提到的建立temp link
    1)哪一个节点是的最后一个节点?@ 一直往右走, 走到->right = nullptr,因为这是一个binary search tree
    2)所以我们只要检验从出发一直往右走,看看能不能回到就知道有没有被遍历过
    3)当我们确定被遍历过后,记得把temp link删除来恢复原来的树,然后就可以确定的顺序,继续探索

基本的Morris遍历的代码

class Solution {
public:
    void recoverTree(TreeNode* curr) {
        // “左中右”
        while (curr)
        {   
            // “左”为空, “中”可以被确定下来了,可以去探索还没被遍历过的“右”了
            if (!curr->left)
            {
                cout << curr->val << " ";
                curr = curr->right;
            }
            // “左”不为空,那么“左”可能还没被遍历过,也可能已经遍历过了
            else
            {
                // 尝试寻找“左”的“temp link”回溯到“中”
                TreeNode *p = curr->left;
                while (p->right && p->right != curr) p = p->right;

                // 没找到,“左”还没被遍历过,所以“中”还不能被确定顺序,
                // 先给“左”的最大的节点设置“temp link”回溯到“中”,再去遍历“左”
                if (!p->right)
                {
                    // 设置temp link @ 等下次再次来到curr时可以意识到左子树已经遍历过了
                    p->right = curr;
                    curr = curr->left;
                }
                // 找到, “左“已经被遍历过了,所以”中“的顺序能被确定
                // 先把”temp link“删掉恢复”左“树,再去遍历还没被遍历过的”右“
                else
                {
                    p->right = nullptr;
                    cout << curr->val << " ";
                    curr = curr->right;
                }
            }
        }
    }
};

lc99 @ 在Morris遍历的基础上,我们只需要在出现逆序对的地方就能找出我们想要的数
1. 交换的是相邻两个数,例如 1 3 2 4 5 6,则第一个逆序对,就是被交换的两个数,这里是3和2;
2. 交换的是不相邻的数,例如 1 5 3 4 2 6,则第一个逆序对的第一个数,和第二个逆序对的第二个数,就是被交换的两个数,这里是5和2;

first, second记录这两个应该被交换的数,用last记录上一个被确定顺序的数。
改法很简单,每次curr被确定时, 做一下逆序对判断然后更新firstsecondlast

// 逆序对判断
if (last && last->val > curr->val)
{
    if (!first) first = last, second = curr;
    else second = curr;
}
last = curr;

最后答案

class Solution {
public:
    void recoverTree(TreeNode* curr) {
        TreeNode *first = nullptr, *second = nullptr, *last = nullptr;
        while (curr)
        {   
            if (!curr->left)
            {
                // 逆序对判断
                if (last && last->val > curr->val)
                {
                    if (!first) first = last, second = curr;
                    else second = curr;
                }
                last = curr;

                curr = curr->right;
            }
            else
            {
                TreeNode *p = curr->left;
                while (p->right && p->right != curr) p = p->right;
                if (!p->right)
                {
                    p->right = curr;
                    curr = curr->left;
                }
                else
                {
                    // 逆序对判断
                    if (last && last->val > curr->val)
                    {
                        if (!first) first = last, second = curr;
                        else second = curr;
                    }
                    last = curr;

                    p->right = nullptr;
                    curr = curr->right;
                }
            }
        }
        swap(first->val, second->val);
    }
};


活动打卡代码 LeetCode 110. 平衡二叉树

acw_zhw
1天前
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        int hl = dfs(root->left, 0);
        int hr = dfs(root->right, 0);
        return res && abs(hl - hr) <= 1;
    }
private:
    int dfs(TreeNode *curr, int depth)
    {
        // base case
        if (!res) return 0;
        if (!curr) return depth;
        // recursion
        int hl = dfs(curr->left, depth + 1);
        int hr = dfs(curr->right, depth + 1);
        if (abs(hl - hr) > 1) res = false;
        return max(hl, hr);
    }
    bool res = true;
};



acw_zhw
1天前

lc108的进阶题 @ 每次选median作为root
可以考虑遍历一遍把list变成array
然后就跟108一毛一样了

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return nullptr;

        auto curr = head;
        for (int i = 0; curr; i ++, curr = curr->next)
            a.push_back(curr);
        return dfs(0, a.size() - 1);
    }
private:
    TreeNode* dfs(int l, int r)
    {
        // base case
        if (l > r) return nullptr;
        if (l == r) return new TreeNode(a[l]->val);
        // recursion
        int m = (l + r) >> 1;
        auto root = new TreeNode(a[m]->val);

        if (m != l) root->left = dfs(l, m - 1);
        if (m != r) root->right = dfs(m + 1, r);

        return root;
    }
    vector<ListNode*> a;
};



acw_zhw
1天前

每次选median [(l + r) >> 1]作为root


class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;
        return dfs(nums, 0, nums.size() - 1);
    }
private:
    TreeNode* dfs(vector<int> &a, int l, int r)
    {
        // base case
        if (l > r) return nullptr;
        if (l == r) return new TreeNode(a[l]);
        // recursion
        int m = (l + r) >> 1;
        auto root = new TreeNode(a[m]);
        if (m != l) root->left = dfs(a, l, m - 1);
        if (m != r) root->right = dfs(a, m + 1, r);

        return root;
    }
};



acw_zhw
1天前

跟lc102,103差不多

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        dfs(root, 0);
        reverse(res.begin(), res.end());
        return res;
    }
private:
    void dfs(TreeNode *curr, int depth)
    {
        if (!curr) return;
        if (depth == res.size()) res.push_back(vector<int>(0));
        res[depth].push_back(curr->val);
        dfs(curr->left, depth + 1);
        dfs(curr->right, depth + 1);
    }
    vector<vector<int>> res;
};



acw_zhw
1天前

inorder @ tells left and right subtrees
postorder @ tells root

跟lc106一样都是可以看着例子来计算各种下标


class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return nullptr;
        return dfs(postorder, 0, postorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* dfs(const vector<int>& postorder, int lp, int rp, 
                  const vector<int>& inorder, int li, int ri)
    {
        // construct current root
        auto root = new TreeNode(postorder[rp]);
        // look up the root in inorder, so we can determine range for left and right tree
        int t = li;
        while (inorder[t] != root->val) t ++;
        // construct left & right subtrees
        if (t != li) root->left = dfs(postorder, lp, t - li + lp - 1, inorder, li, t - 1);
        if (t != ri) root->right = dfs(postorder, t - li + lp, rp - 1, inorder, t + 1, ri);
        return root;
    }
};



acw_zhw
1天前

preorder @ tells us root
inorder @ tells us left subtree and right subtree

用给的例子来计算各种下标

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0) return nullptr;
        return dfs(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
private:
    TreeNode* dfs(const vector<int>& preorder, int lp, int rp, 
                  const vector<int>& inorder, int li, int ri)
    {
        // construct current root
        auto root = new TreeNode(preorder[lp]);
        // look up the root in inorder, so we can determine range for left and right tree
        int t = li;
        while (inorder[t] != root->val) t ++;
        // construct left & right subtrees
        if (t != li) root->left = dfs(preorder, lp + 1, lp + t - li, inorder, li, t - 1);
        if (t != ri) root->right = dfs(preorder, lp + t - li + 1, rp,inorder, t + 1, ri);
        return root;
    }
};



acw_zhw
1天前
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return dfs(root, 1);
    }
private:
    int dfs(TreeNode *curr, int depth)
    {
        int maxv = depth;
        if (curr->left) maxv = dfs(curr->left, depth + 1);
        if (curr->right) maxv = max(maxv, dfs(curr->right, depth + 1));
        return maxv;
    }
};



acw_zhw
1天前
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        dfs(root, 0);
        for (int i = 1; i < res.size(); i += 2)
            reverse(res[i].begin(), res[i].end());

        return res;
    }
private:
    void dfs(TreeNode *curr, int depth)
    {
        if (!curr) return;
        if (depth == res.size()) res.push_back(vector<int>(0));

        res[depth].push_back(curr->val);
        dfs(curr->left, depth + 1);
        dfs(curr->right, depth + 1);
    }
    vector<vector<int>> res;
};



acw_zhw
1天前

可以dfs也可以bfs
dfs的话按深度来push back
bfs的话queue存node

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root, 0);
        return res;
    }
private:
    void dfs(TreeNode *curr, int depth)
    {
        if (!curr) return;
        if (depth == res.size()) res.push_back(vector<int>(0));
        res[depth].push_back(curr->val);
        dfs(curr->left, depth + 1);
        dfs(curr->right, depth + 1);
    }
    vector<vector<int>> res;
};