Leetcode - 7 - (nearest common ancestor of binary tree, rotation array, direct of binary tree, next permutation, combined sum)

class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root==NULL) return 0;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if((lson&&rson)||((root->val==p->val||root->val==q->val)&&(lson||rson))) ans = root;
        return lson||rson||(root->val==p->val||root->val==q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q); // Traversing down from a root node can encounter pq Two nodes 
        return ans;
    }
};

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.begin()+n);
        reverse(nums.begin(), nums.begin()+k);
        reverse(nums.begin()+k, nums.begin()+n);
    }
};

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

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size()-2;
        while(i>=0&&nums[i]>=nums[i+1]) i --;
        if(i>=0){
            int j = nums.size()-1;
            while(j>=0&&nums[i]>=nums[j]) j --;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin()+i+1, nums.end());

    }
};

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> res;
    void dfs(vector<int>& candidates, int target, int idx){
        if(candidates.size()==idx) return;
        if(target==0){
            ans.push_back(res);
            return;
        }
        dfs(candidates, target, idx+1); // Just skip 
        if(target-candidates[idx]>=0){
            res.push_back(candidates[idx]); // Select the current value 
            dfs(candidates, target-candidates[idx], idx);
            res.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return ans;
    }
};