zkkKillua's Blog
0%

发表于 更新于 分类于

1. 普通二叉树的最近公共祖先

参照“236.二叉树的最近公共祖先”，可以使用递归或迭代求解。

递归求解是到左右子树中查找有无给定的p和q节点，根据不同的条件返回指针。
迭代求解是使用hash表记录各节点的父节点，然后比较p和q的各祖先节点，可以是朴素比较/记录层数/记录是否访问。

2. 迭代

如果p或q等于当前节点，返回当前节点。
如果p和q都小于或者都大于当前节点，则到左子树或右子树中查找。
如果p和q一个大于当前节点，一个小于当前节点，说明p和q在当前节点处分开，则当前节点一定是二者的最近公共祖先。
相较于普通的二叉树，利用二叉搜索树的性质减少了对不必要的分支的访问。
时间O(n)，空间O(1)。

阅读全文 »

发表于 分类于

1. 递归

递归到以当前root为根的子树中查找是否包含p或q节点。
因为包含与否分四种情况：都不包含，只含p，只含q，都包含。
因此只用简单的true/false是不容易表示的，因此可以考虑返回指针，分别返回：null, &p, &q, root。
时间O(n)，空间O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr)
            return nullptr;
        
        if (root->val == p->val || root->val == q->val)
            return root;

        TreeNode* leftTree = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightTree = lowestCommonAncestor(root->right, p, q);

        if (leftTree == nullptr)
            return rightTree;
        else if (rightTree == nullptr)
            return leftTree;
        else
            return root;
    }
};

2. 迭代

使用hash表记录每个节点的parent，然后分别找p和q节点的parent一直到整棵树的root，在此过程中查找最近公共祖先。
这就相当于在两个数组中查找最接近开始位置的相等值的位置。

阅读全文 »

发表于 分类于

1. 递归+回溯

类似于“112.路经总和”，不过要记录路径上的各个点。
只需要在原有递归访问子节点并修改目标值的基础上，增加把当前节点加入数组的过程即可，在回到上一层时需要回溯。
时间O(n^2)，空间O(n^2) 

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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }
private:
    void dfs(TreeNode* root, int sum) {
        if (root == nullptr)
            return;
        
        subAns.push_back(root->val);

        if (root->left == nullptr && root->right == nullptr && root->val == sum) 
            ans.push_back(subAns);

        if (root->left != nullptr) 
            dfs(root->left, sum - root->val);
        if (root->right != nullptr)
            dfs(root->right, sum - root->val);
        
        subAns.pop_back();
    }
    vector<int> subAns;
    vector<vector<int>> ans;
};

2. 迭代

层次遍历的访问方法，同“112.路径总和”的迭代访问一样，使用队列同时暂存对应的节点和当前目标值。
此外，由于这道题还需要获得具体路径，因此还需要一个额外的队列记录开头到当前节点的路径。

阅读全文 »

发表于 分类于

1. 递归

递归访问子节点，同时修改目标值。
需要注意的是空节点被看作空，而不是0，所以需要调整边界条件的判断。
时间O(n)，空间O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == nullptr)
            return false;
        if (root->left == nullptr && root->right == nullptr)
            return root->val == sum;

        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
};

2. 迭代

使用队列暂存节点和当前的目标值，不断访问队首元素，判断其是否为叶子节点以及将其子节点和对应目标值入队列。
时间O(n)，空间O(n)。

阅读全文 »

发表于 分类于

1. 递归

参照“105. 从前序与中序遍历序列构造二叉树”。
中序遍历：左根右
后序遍历：左右根

从后序遍历结尾处获得当前的根节点，然后到中序遍历中查找根节点的位置，并以此划分中序和后序序列为左右子树两部分。
同时使用hash表优化，避免每次都要遍历中序序列才能找到根节点，降低时间复杂度。
时间O(n)，空间O(n)。 

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
/**
 * 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:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();
        for (int i = 0; i < n; i++) 
            index[inorder[i]] = i;
        
        return buildTree(postorder, 0, n - 1, 0, n - 1);
    }
private:
    TreeNode* buildTree(vector<int>& postorder, int ibegin, int iend, int pbegin, int pend) {
        if (ibegin > iend)
            return nullptr;
        
        TreeNode* root = new TreeNode(postorder[pend]);
        int leftCount = index[postorder[pend]] - ibegin;
        root->left = buildTree(postorder, ibegin, ibegin + leftCount - 1, pbegin, pbegin + leftCount - 1);
        root->right = buildTree(postorder, ibegin + leftCount + 1, iend, pbegin + leftCount, pend - 1);

        return root;
    }
    unordered_map<int, int> index;
};

发表于 分类于

1. 递归

前序遍历是根左右，因此前序序列的首个字符为根节点，之后一部分是左子树的节点，左子树部分的右侧一部分是右子树节点。
中序遍历是左根右，因此中序遍历的开头一部分是左子树的节点，然后是根节点，之后剩下的右部分是右子树的节点。

因此可以首先根据前序遍历的首个字符，确定根节点。
然后在中序序列中找到根节点，其左侧的部分就是左子树的节点，右侧部分就是右子树的节点。
根据中序序列中左右部分的长度，就可以在前序序列中划分出左右子树的部分。
然后递归构造即可。
时间O(n^2)，空间O(n)。

因为每次都要遍历中序序列，找到当前的root，所以时间复杂度比较高。
因此可以使用hash预先处理中序序列，之后每次就能用O(1)的方法查找到当前的root，时间复杂度降低到O(n)。
unordered_map<序列中的值, 该值对应在序列中的位置> 

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
/**
 * 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:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++)
            index[inorder[i]] = i;

        return buildTree(preorder, 0, n - 1, 0, n - 1);
    }
private:
    TreeNode* buildTree(vector<int>& preorder, int pstart, int pend, int istart, int iend) {
        if (pstart > pend)
            return nullptr;
        
        TreeNode* root = new TreeNode(preorder[pstart]);
        int leftCount = index[preorder[pstart]] - istart;
        root->left = buildTree(preorder, pstart + 1, pstart + leftCount, istart, istart + leftCount - 1);
        root->right = buildTree(preorder, pstart + leftCount + 1, pend, istart + leftCount + 1, iend);

        return root;
    }
    unordered_map<int, int> index;
};

发表于 分类于

1. 中序遍历+辅助数组

中序遍历获得有相同值的BST的非严格递增序列，存入辅助数组中，然后统计众数。
时间O(n)，空间O(n)。

2. 中序遍历

在中序遍历的过程中，可以直接记录和统计当前数据的出现次数，跟之前出现过的最大次数比较即可，不需要辅助数组。
时间O(n)，空间O(n)。 

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
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        if (root == nullptr)
            return {};
        vector<int> ans;
        stack<TreeNode*> st;
        int maxMode, maxCount = 0;
        int cur, curCount = 0;

        while (root != nullptr || !st.empty()) {
            if (root == nullptr) {
                root = st.top();
                st.pop();
                if (cur == root->val)
                    curCount++;
                else {
                    cur = root->val;
                    curCount = 1;
                }
                if (curCount == maxCount) 
                    ans.push_back(cur);
                else if (curCount > maxCount) {
                    maxCount = curCount;
                    if (maxMode != cur) {
                        maxMode = cur;
                        ans.clear();
                        ans.push_back(maxMode);
                    }
                }
                root = root->right;
            } else {
                st.push(root);
                root = root->left;
            }
        }

        return ans;
    }
};

发表于 分类于

1. 递归

合并两棵二叉树相当于新建一个值为两棵二叉树根节点值和的根节点，然后递归合并左子树和右子树。
时间O(m + n)，空间O(m + n)。 

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
/**
 * 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:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr)
            return nullptr;
        
        TreeNode* root = new TreeNode(0);
        if (t1 != nullptr)
            root->val += t1->val;
        if (t2 != nullptr)
            root->val += t2->val;
        
        root->left = mergeTrees(t1 == nullptr ? nullptr : t1->left, t2 == nullptr ? nullptr : t2->left);
        root->right = mergeTrees(t1 == nullptr ? nullptr : t1->right, t2 == nullptr ? nullptr : t2->right);

        return root;
    }
};

发表于 分类于

1. 中序遍历

BST的中序遍历得到的结果是从小到大的有序序列，可以使用一个数组记录这个序列，然后遍历BST，对每个节点累加值。
为了降低累加过程需要的时间，可以使用hash表统计大于各个值的节点值之和，从而避免每次都要重新求和。
时间O(n)，空间O(n)。 

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
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (root == nullptr)
            return root;

        vector<int> vals;
        midOrder(root, vals);
        unordered_map<int, int> sum;
        int temp = 0;
        for (int i = vals.size() - 1; i >= 0; i--) {
            temp += vals[i];
            sum[vals[i]] = temp;
        }

        queue<TreeNode*> q;
        q.push(root);
        TreeNode* cur;
        while (!q.empty()) {
            cur = q.front();
            q.pop();
            cur->val = sum[cur->val];
            if (cur->left != nullptr)
                q.push(cur->left);
            if (cur->right != nullptr)
                q.push(cur->right);
        }

        return root;
    }
private:
    void midOrder(TreeNode* root, vector<int>& vals) {
        stack<TreeNode*> st;
        while (root != nullptr || !st.empty()) {
            if (root == nullptr) {
                root = st.top();
                st.pop();
                vals.push_back(root->val);
                root = root->right;
            } else {
                st.push(root);
                root = root->left;
            }
        }
    }
};

2. 反向中序遍历

要修改一个节点需要获取比这个节点大的值，比它大的值在它的右子树中，同时还来自于它的各层父节点（如果它是父节点的左孩子的话）。
如果按照这个思路求解每个节点的比它大的所有值是有些困难的，但是联想到中序遍历得到的有序序列就会比较简单。
中序左根右遍历BST得到的是由小到大的有序序列，因此反向中序右根左遍历BST得到的是由大到小的有序序列。
题目需要的比每个节点大的值正好由反向中序遍历提供了。
时间O(n)，空间O(n)。

阅读全文 »

发表于 分类于

1. group by

因为要求保留每种邮箱中最小的Id，因此只需要根据邮箱分组，筛选出每组邮箱最小的Id，然后删除不是最小的Id即可。 

1
2
3
4
5
6
7
8
delete from Person
where Id not in (
    select t.Id from (
        select min(Id) as Id
        from Person
        group by Email
    ) t
);

2. 自连接

使用delete t1 from t1, t2 where..语句，而不是delete from t1 where...语句。
这条语句不是从t1和t2表连接得到的临时表中删除数据，而是根据where的条件从删除t1中的数据，from只是方便where的条件。

阅读全文 »