Sum root to leaf numbers -- Leetcode

Question:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Answer:

class Solution {

public:

    int sumNumbers(TreeNode *root) {

        vector<vector<int>> res;

        vector<int> a;

        path(root,a,res);

        

        int sum=0;

        int len=res.size();

        for(int i=0;i<len;i++){

            sum+=StrToInt(res[i]);

        }

        return sum;

    }

    

    void path(TreeNode *root,vector<int> &a,vector<vector<int>> &res){

        if(!root)return;

        

        else{

        a.push_back(root->val);

        

        if(root->left){

            path(root->left,a,res);

        }

        

        if(root->right){

            path(root->right,a,res);

        }

        

        if(!root->left&&!root->right&&root){

            vector<int> b=a;

            res.push_back(b);

        }

        

        a.pop_back();

        return;

        }

    }

    

    int StrToInt(vector<int> s) {

        int len=s.size();

        int res=0;

        for(int i=0;i<len;++i){

            int j=len-i-1;

            int num=s[i];

            while(j>0){

                num=num*10;

                --j;

            }

            res+=num;

        }

        return res;

    }

};

Linked List Cycle II -- Leetcode

Question:

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

Answer:

class Solution {

public:

    ListNode *detectCycle(ListNode *head) {

        ListNode *slow=head, *fast=head;

    

       while(slow&&fast&&fast->next){

            slow=slow->next;

            fast=fast->next->next;

            if(slow==fast)

                break;

        }

        

        if(!slow||!fast||!fast->next){

            return NULL;

        }

        

        slow=head;

        while(slow!=fast){

            slow=slow->next;

            fast=fast->next;

        }

        return slow;

    }

};

Flatten BT to linked list -- Leetcode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Answer:
Using recursion, need O(n) space.

class Solution {
public:
    void flatten(TreeNode *root) {
         TreeNode *end = flattenHelp(root);
         return;
    }
   
    TreeNode* flattenHelp(TreeNode* root){
        if(!root) return NULL;
   
        TreeNode *left = root->left;
        TreeNode *right = root -> right;
       
        if(!left && !right) return root;
       
        else if(!left && right){
            return flattenHelp(right);
        }
       
        else if(left && !right){
             TreeNode *leftend = flattenHelp(left);
             root->right = left;
             root->left = NULL;
             return leftend;
        }
        else{
        TreeNode *leftend = flattenHelp(left);
        TreeNode *rightend = flattenHelp(right);
        root->right = left;
        root->left = NULL;
        leftend ->right = right;
        return rightend;
        }
    }
};

Path Sum -- Leetcode

Question:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Answer:

class Solution {

public:

    bool hasPathSum(TreeNode *root, int sum) {

        if(!root)return false;

        else if(!root->left&&!root->right&&root->val==sum) return true;

        else{

            if(hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val)){

                return true;

            }

            else

               return false;

        }

    }

};

Merge Two sorted list -- Leetcode

Answer:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

        if(!l1)return l2;

        if(!l2)return l1;

        

        ListNode *dummy=new ListNode(0);

        dummy->next=l1;

        ListNode *prev=dummy;

        ListNode *p=l1;

        ListNode *q=l2;

        ListNode *qnext=NULL;

        while(p&&q){

            if(p->val<=q->val){

                prev=p;

                p=p->next;

            }

            else{

                qnext=q->next;

                prev->next=q;

                q->next=p;

                prev=q;

                q=qnext;

            }

        }

        if(q){

            prev->next=q;

        }

        return dummy->next;

    }

};