437. Path Sum III (easy)

Q:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

A:

这个是错的，具体是为什么呢？ 答案看最下方

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root)
            return 0;
        
        int endHere = sum == root->val? 1:0;
        return pathSum(root->left, sum-root->val) + 

               pathSum(root->right, sum-root->val) + 

               pathSum(root->left, sum) + 

               pathSum(root->right, sum) + endHere;
    }
};

my real solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root)
            return 0;
        
        return pathSum(root->left, sum) + 

               pathSum(root->right, sum) + 

               directSum(root,sum);
    }
private:
    int directSum(TreeNode* root, int sum)
    {
        if(!root)
            return 0;
        int endHere = sum==root->val?1:0;
        return directSum(root->left, sum-root->val) + directSum(root->right, sum-root->val) + endHere;
    }
};

为啥错呢？   因为在递归的时候，把一些路径计算了2次。

617. Merge Two Binary Trees (easy)

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

 

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

 

Constraints:

• The number of nodes in both trees is in the range [0, 2000].
• -104 <= Node.val <= 104

A:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1)
            return t2;
        if(!t2)
            return t1;
        auto l = mergeTrees(t1->left, t2->left);
        auto r = mergeTrees(t1->right, t2->right);
        auto *root = new TreeNode(t1->val + t2->val， l，r );

        return root;
    }
};

---------第二遍-----------------------

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {

if(!root1 && !root2)

return nullptr;

TreeNode* root = new TreeNode( (root1? root1->val:0) + (root2? root2->val:0));

root->left = mergeTrees(root1?root1->left:nullptr, root2?root2->left:nullptr);

root->right =mergeTrees(root1?root1->right:nullptr,root2?root2->right:nullptr);

return root;

}

};

Mistakes:

        auto *root = new TreeNode(t1->val + t2->val);

这一句，一开始写的时候，错写成了
               TreeNode *root(t1->val + t2->val)
而且注意：这里的 new  是一定要写的。 否则，我们method

543. Diameter of Binary Tree. (Easy)

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

 

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

A:

 利用C++ 的参数reference type, 来完成 多个 返回值

看helper(     , int & maxDepth)

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int diameterOfBinaryTree(TreeNode* root) {

int maxDiameter = 0;

helper(root, maxDiameter);

return maxDiameter;

}

private:

int helper(TreeNode* root, int& maxVal) { // return depth of the tree

if (!root)

return 0;

int dl = helper(root->left, maxVal);

int dr = helper(root->right, maxVal);

if (dl + dr > maxVal) {

maxVal = dl + dr;

}

return 1 + max(dl, dr);

}

};

1281. Subtract the Product and Sum of Digits of an Integer (easy)

Q:

Given an integer number n, return the difference between the product of its digits and the sum of its digits.

Example 1:

Input: n = 234
Output: 15 
Explanation: 
Product of digits = 2 * 3 * 4 = 24 
Sum of digits = 2 + 3 + 4 = 9 
Result = 24 - 9 = 15

Example 2:

Input: n = 4421
Output: 21
Explanation: 
Product of digits = 4 * 4 * 2 * 1 = 32 
Sum of digits = 4 + 4 + 2 + 1 = 11 
Result = 32 - 11 = 21

Constraints:

• 1 <= n <= 10^5

A:

class Solution {
public:
    int subtractProductAndSum(int n) {
        int pro=1, sum =0;
        while(n)
        {
            int v = n%10;
            n /= 10;
            pro *= v;
            sum += v;
        }
        return pro - sum;        
    }
};

1287. Element Appearing More Than 25% In Sorted Array (easy)

Q:

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.

Return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6

Constraints:

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^5

A:

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int curVal = arr[0];
        int count =0;
        int one4 = arr.size()/4;
        for(auto v:arr)
        {
            if(v == curVal)
            {
                count++;
                if(count > one4)
                {
                    return curVal;
                }
            }else{
                count =1;
                curVal = v;
            }
        }
        return -1; // should never hit
    }
};

1290. Convert Binary Number in a Linked List to Integer (easy)

Q:

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

Example 1:

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0]
Output: 0

Example 3:

Input: head = [1]
Output: 1

Example 4:

Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880

Example 5:

Input: head = [0,0]
Output: 0

Constraints:

• The Linked List is not empty.
• Number of nodes will not exceed 30.
• Each node's value is either 0 or 1.

A:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode *runner = head;
        int res = 0;
        while(runner != NULL)
        {
            res = res*2 + runner->val;
            runner = runner->next;
        }
        return res;
    }
};

1295. Find Numbers with Even Number of Digits (easy)

Q:

Given an array nums of integers, return how many of them contain an even number of digits.

Example 1:

Input: nums = [12,345,2,6,7896]
Output: 2
Explanation: 
12 contains 2 digits (even number of digits). 
345 contains 3 digits (odd number of digits). 
2 contains 1 digit (odd number of digits). 
6 contains 1 digit (odd number of digits). 
7896 contains 4 digits (even number of digits). 
Therefore only 12 and 7896 contain an even number of digits.

Example 2:

Input: nums = [555,901,482,1771]
Output: 1 
Explanation: 
Only 1771 contains an even number of digits.

Constraints:

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 10^5

A:

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int res=0; 
        for(auto v : nums)
        {
            string s = to_string(v);
            if(s.length() %2==0)
                res++;
        }
        return res;
    }
};

Learned:
int res;  如果不显示声明为0， 的话，会有奇怪的结果。  in method, no default value.