lc-day6

发表于

563. 二叉树的坡度

没想清除一个点，被卡了好久，二叉树的遍历别看只有短短几行代码，递归起来是真的要命，不好debug就很麻烦了，准备后期放假了玩命刷，现在就尽量把每题精刷一遍

图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int ans;
    int findTilt(TreeNode* root) {
        if(root == nullptr) return 0;
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root){
        //if(root->left == nullptr && root->right == nullptr) return root->val;
        int l = 0, r = 0;
        if(root->left) l = dfs(root->left);
        if(root->right) r = dfs(root->right);
        ans += abs(l - r);
        return l + r + root->val;
    }
};

没想清楚的是【递归返回值】，我错误地认为【返回值】能干同时干两件事：返回正确答案+能跑递归代码。实际上只能干一件事，就是跑代码。题目的答案则需要用一个ans另外计算

递归水太深，把握不住

654.最大二叉树

构建二叉树只会写模板题，还要加强练习

题目

题目

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* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1){
            node->val = nums[0];
            return node;
        }

        int maxValue = 0, maxIndex = 0;
        for(int i = 0; i < nums.size(); i++){
            if(maxValue < nums[i]) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        node->val = maxValue;
        //保证左边有一个节点
        if(maxIndex > 0){
            vector<int> newVec(nums.begin(), nums.begin() + maxIndex);
            node->left = constructMaximumBinaryTree(newVec);
        }
        //保证右边有一个节点
        if(maxIndex < (nums.size() - 1)){
            vector<int> newVec(nums.begin() + maxIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

简单暴力的写法，思路清晰，还学到一个技巧，动态数组还能这么玩

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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return dfs(nums, 0, nums.size());
    }

    TreeNode* dfs(vector<int>& nums, int left, int right){
        //左闭右开区间
        if(left >= right) return nullptr;
        TreeNode* node = new TreeNode(0);
        int maxIndex = left;
        for(int i = left + 1; i < right; i++){
            if(nums[maxIndex] < nums[i]) {
                maxIndex = i;
            }
        }
        node->val = nums[maxIndex];
        //实际取值区间【left， maxIndex - 1】
        node->left = dfs(nums, left, maxIndex);
        //实际取值区间【maxIndex + 1， right - 1】
        node->right = dfs(nums, maxIndex + 1, right);
        //这样就把中间值maxIndex跳过去了
        return node;

    }
};

第二种方法把空节点引入到了递归中，所以省去了两个if条件

617. 合并二叉树

题目

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == nullptr && root2 == nullptr) return NULL;
        if(root1 == nullptr || root2 == nullptr) return root2 == nullptr ? root1 : root2;
        root1->val += root2->val;
        root1->left = mergeTrees(root1->left, root2->left);
        root1->right = mergeTrees(root1->right, root2->right);
        return root1;
    }
};

将root2树上的值移到root1树上就行了

700. 二叉搜索树中的搜索

题目

白给题

递归法

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

    }
};

迭代法

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root != NULL){
        	if(root->val > val) root = root->left;
        	else if(root->val < val) root = root->right;
        	else return root;
        }
        return NULL;
    }
};

98. 验证二叉搜索树

题目

踩陷阱啦，我憨憨地用递归直接进行判断，左边val小右边val大，然后直接gg

正确思路应该是用中序遍历把它输出成数组，然后在数组里面判断是否是严格递增序列，不是判false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> result;
    bool isValidBST(TreeNode* root) {
        dfs(root);
        if(judge(result)) return true;
        return false;
    }
    void dfs(TreeNode* root){
        if(root == nullptr) return;
        dfs(root->left);
        result.push_back(root->val);
        dfs(root->right);
    }
    bool judge(vector<int>& res){
        for(int i = 0; i < res.size() - 1; i++)
            if(res[i] >= res[i + 1]) return false;
        return true;
    }
};

今天就到这吧