[leetcode] mimimum depth of binary tree

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        if (!root)
            return 0;
       
        queue my_queue;
        my_queue.push(root);
        my_queue.push(NULL);
        int depth = 0, min_depth = 9999;
       
        while (!my_queue.empty())
        {
            TreeNode *front = my_queue.front();
           
            my_queue.pop();
           
            if (!front)
                depth++;
            else
            {
                if (!front->left && !front->right)
                {
                    if (min_depth > depth)
                        min_depth = depth;
                }
                if (front->left) my_queue.push(front->left);
                if (front->right) my_queue.push(front->right);
                front = my_queue.front();
                if (!front) my_queue.push(NULL);
            }
        }
       
        min_depth++;
       
        return min_depth;
    }
};

[leetcode] maximum depth of binary tree

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        if (!root)
            return 0;
       
        // level traversal
       
        queue my_queue;
       
        my_queue.push(root);
        my_queue.push(NULL); // a dummy node
       
        int depth = 0;
       
        while (!my_queue.empty())
        {
            TreeNode *front = my_queue.front();
            my_queue.pop();
            if (!front)
            {
                depth++;
            }
            else
            {
                if (front->left) my_queue.push(front->left);
                if (front->right) my_queue.push(front->right);
                front = my_queue.front();
                if (!front) my_queue.push(NULL);
            }
        }
       
        // reduce by 1 because of the last dummy node
        depth--;
       
        return depth;
    }
};

[leetcode] longest common prefix

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

这个简单，差不多一遍通过：）


class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
     
        if (strs.empty())
        {
            return string("");
        }
     
        // first find the minimum string length
        int min_len = strs[0].length();
     
        for (int i = 0; i < strs.size(); i++)
        {
            if (min_len > strs[i].length())
                min_len = strs[i].length();
        }
     
        // compare staring at [min_len-1]
        int length = 0;
        for (int index = 0; index < min_len; index++)
        {
            bool all_equal = true;
            for (int cur = 1; cur < strs.size(); cur++)
            {
                if (strs[cur-1][index] != strs[cur][index])
                {
                    all_equal = false;
                    break;
                }
            }
            if (all_equal)
                length = index + 1;
            else
                break;
        }
     
        return strs[0].substr(0,length);
    }
};

[leetcode] count and say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

class Solution {
public:
    string countAndSay(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        string str = "1";
       
        if (n == 1)
            return str;
       
        for (int i = 1; i < n; i++)
        {
            string new_str = "";
            int count = 0;
            char ch, pre = '0';
            bool flag = false;
           
            for (int k = 0; k < str.length(); k++)
            {
                ch = str[k];
               
                if (ch == pre || k == 0)
                {
                    count++;
                }
               
                if ( (k > 0 && ch != pre ) || k == str.length()-1)
                {
                    flag = true;
                }
               
                if (flag)
                {
                    // update new_str
                    char tmp = '0' + count;
                    new_str += tmp;
                    if (k > 0)
                        new_str += pre;
                    else
                        new_str += ch;
                    count = 1;
                    flag = false;
                }
               
                // check the last character
                if ( k > 0 && k == str.length()-1 && ch != pre)
                {
                    // we know we have to process the
                    new_str += '1';
                    new_str += ch;
                }
               
                pre = ch;
            }
           
            // update str
            str = new_str;
        }
       
        return str;
    }
};

[leetcode] unique binary search trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int cache[n];
       
        for (int i = 0; i < n; i++)
            cache[i] = 0;
       
        cache[0] = 1;
       
        for (int i = 1; i < n; i++)
        {
            // compute the count for N = i+1 nodes
            int count = 0;
            for (int k = 0; k <= i; k++)
            {
                // assume [0..i] is computed
                // pick k as the root
                int left_sum = 1, right_sum = 1;
               
                if (k > 0)
                    left_sum = cache[k-1];
               
                if (k < i)
                    right_sum = cache[i-k-1];
                   
                count += left_sum*right_sum;
            }
            cache[i] = count;
        }
       
        return cache[n-1];
    }
};

[leetcode] flatten binary tree to linked list

Flatten Binary Tree to Linked List

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // use a 'pre' pointer to track the predecessor of the current node
        // use pre-order traversal
       
        if (!root)
            return;
       
        stack my_stack;
        TreeNode *pre = NULL;
       
        my_stack.push(root);
        while (!my_stack.empty())
        {
            TreeNode *p = my_stack.top();
           
            // visit p
            if (pre)
            {
                pre->right = p;
                pre->left = NULL;
            }
           
            pre = p;
           
            // pop current node
            my_stack.pop();
           
            // push right and left children into stack
            if (p->right) my_stack.push(p->right);
            if (p->left) my_stack.push(p->left);
        }
    }
};

[leetcode] search for a range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

class Solution {
public:
    vector searchRange(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // binary search in the given array
        int start = 0, end = n-1, mid;
        vector result;
        bool is_found = false;
        int c1 = -1, c2 = -1;
       
        while (start <= end)
        {
            mid = (start + end) / 2;
           
            if (target == A[mid])
            {
                is_found = true;
                break;
            }
            else if (target > A[mid])
                start = mid + 1;
            else
                end = mid - 1;
           
        }
       
        if (is_found)
        {
            // move cursors
            c1 = mid, c2 = mid;
            while (A[c1] == target && c1 >= 0)
                c1--;
            while (A[c2] == target && c2 < n)
                c2++;
            c1++;
            c2--;
        }
       
        result.push_back(c1);
        result.push_back(c2);
       
        return result;
    }
};