lc-day8

发表于

236. 二叉树的最近公共祖先

题目

这个题直接g， 好久之前写的全忘了，方法太巧妙了

没做出来之前好难，看完了Carl的题解后，只想说两个点

返回值：这题居然是遍历整棵二叉树还附带返回值，在之前的题目中Carl的结论是【有返回值的递归是部分遍历】，这题发生了变化

回溯，自底向上。这道题拿到后很容易想到从底部向上移动，找出祖先节点。但这题给的条件是树的根节点，而且树是单向的，你没有第二个指针遍历回去，那怎么办呢？解决办法是回溯，既然有向下递归，那就有向上回溯，只要你进去了，总归是要出来的，然后向上返回就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != NULL && right != NULL) return root;
        else if(left == NULL && right != NULL) return right;
        else if(left != NULL && right == NULL) return left;
        else return NULL;

    }
};

594. 最长和谐子序列

每日一题

打卡题，不过还是被迷惑了一会

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    unordered_map<int, int> p;
    int findLHS(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) p[nums[i]]++;
        int maxx = 0;
        for(auto& [x, cnt] : p) 
            if(p.count(x + 1))
            maxx = max(maxx, p[x] + p[x + 1]); 
        return maxx;
    }
};

235. 二叉搜索树的最近公共祖先

题目

这道题结合了二叉搜索树的性质，根据根节点的值决定递归遍历左子树或右子树

这题我只想说一点，部分遍历的问题

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val > p->val && root->val > q->val){
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            if(left) return left;
        }
        if(root->val < p->val && root->val < q->val) {
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            if(right) return right;
        }
        return root;
    }
};

701. 二叉搜索树中的插入操作

题目

基本的题目, 不过更高阶的做法写不出来

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
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        insert(root, val);
        return root;
    }

    void insert(TreeNode* root, int val){
        if(root->val > val){
            if(root->left == nullptr) {
                TreeNode* node = new TreeNode(val);
                root->left = node;
                return;
            }
            insert(root->left, val);
        } 
        if(root->val < val){
            if(root->right == nullptr) {
                TreeNode* node = new TreeNode(val);
                root->right = node;
                return;
            }
            insert(root->right, val);
        } 
    }
};

Carl的解法, 不愧是acm大神

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr){
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root->val > val) root->left = insertIntoBST(root->left, val);
        if(root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};