Day13 左旋转字符串+二叉树的深度+二叉树中和为某一值的路径

TODO:

1. 左旋转字符串，余数的方法可以再看看
2. 重做 二叉树中和为某一值的路径（就是一道典型递归)

剑指 Offer 58 - II. 左旋转字符串(简单)

确实简单，但是感觉这样做面试的时候会不Okay。

reverse函数功能是逆序（或反转），多用于字符串、数组、容器。头文件是#include <algorithm>。
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数无返回值。

class Solution {
public:
    string reverseLeftWords(string s, int n) {
       if(s.empty() || n>s.size()) return s;
       if(n == s.size()) { reverse(s.begin(),s.end()); return s;}
       reverse(s.begin(),s.begin()+n);
       reverse(s.begin()+n,s.end());
       reverse(s.begin(),s.end());
       return s;

    }
};

然后又去看题解
感觉取余数的方法就很妙

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        string res = "";
        for(int i = n; i < n + s.size(); i++){
            res += s[i%s.size()];
        }
        return res;

    }
};

剑指 Offer 55 - I. 二叉树的深度(简单)

超级简单的两行递归。在于树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度 中的 最大值 +1 。
动画演示

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

剑指 Offer 34. 二叉树中和为某一值的路径(中等)

做了好久,大概四十多分钟？然而效果不怎么好，可能因为我是值传递？

image.png

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root == nullptr)return{};
         vector<int> temp;
         dfs(root,target,temp);  
         return res;
    }
    void dfs(TreeNode* root, int target,vector<int> temp){
        if(root == nullptr) return ;
        else{      
            target = target-root->val;
            temp.push_back(root->val);
        }
        if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
            res.push_back(temp);
            return ;
        };
        dfs(root->left, target,temp);
        dfs(root->right,target,temp); 
    }
};

改良版:⭐

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root == nullptr)return{};
         dfs(root,target);  
         return res;
    }
    void dfs(TreeNode* root, int target){
        if(root == nullptr) return ;      
        target = target-root->val;
        path.push_back(root->val);
        if((root->left ==nullptr) && target ==0 && (root->right ==nullptr) ){
            res.push_back(path);
            path.pop_back();//注意这个pop_back()；因为return会导致不能pop_back();从而影响回溯
            return ;
        };
        dfs(root->left, target);
        dfs(root->right,target);
        path.pop_back(); 
    }
};