[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;
    }
};

用栈操作遍历二叉树的方法

先序遍历。将根节点入栈，考察当前节点（即栈顶节点），先访问当前节点，然后将其出栈（已经访问过，不再需要保留），然后先将其右孩子入栈，再将其左孩子入栈（这个顺序是为了让左孩子位于右孩子上面，以便左孩子的访问先于右孩子；当然如果某个孩子为空，就不用入栈了）。如果栈非空就重复上述过程直到栈空为止，结束算法。

中序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过（有标记），则将其左孩子入栈，否则访问当前节点并将其出栈，再将右孩子入栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

后序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过，则将其左孩子入栈，否则如果其右孩子未被访问过，则将其右孩子入栈，如果都已经访问过，则访问其自身，并将其出栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

[leetcode] binary tree maximum path sum

Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Here I consider a recursive solution. We update the 'val' field of each node with the path sum ending at that node (starting from any one of its descendants). We keep a 'max_sum' variable to save the current maximum path sum. We update this variable using paths going through the node, paths ending at this node, and the single-node path. We traverse the binary tree once, so the time complexity is O(n).

/**
 * 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 max_path_helper(TreeNode *root, int &max_sum)
    {
        if (!root) return;
        else
        {
            max_path_helper(root->left, max_sum);
            max_path_helper(root->right, max_sum);
           
            int left_sum = 0, right_sum = 0;
            if (root->left)
                left_sum = (root->left)->val;
            if (root->right)
                right_sum = (root->right)->val;
           
            // update max sum
            int sum = left_sum + right_sum + root->val;
            int sum_left = left_sum + root->val;
            int sum_right = right_sum + root->val;
           
            if (max_sum < sum)
                max_sum = sum;
               
            if (max_sum < sum_left)
                max_sum = sum_left;
           
            if (max_sum < sum_right)
                max_sum = sum_right;
               
            if (max_sum < root->val)
                max_sum = root->val;
           
            // compare with child sums and single value at this node
            int tmp = 0;
            if (left_sum > right_sum)
                tmp = root->val + left_sum;
            else
                tmp = root->val + right_sum;
               
            // update value
            if (tmp > root->val)
                root->val = tmp;
        }
       
    }
   
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // current max sum
        int max_sum = -999;
       
        // for each node, compute the max sum of the path starting at this node
        // update max_sum using the max_sum's of its two subtrees
        if (!root)
            return 0;
           
        max_path_helper(root, max_sum);
       
        // finally compare the current max sum with the path sum ending at root
        if (max_sum < root->val)
            max_sum = root->val;
           
        return max_sum;
    }
};

[leetcode] binary tree level traversal

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector > levelOrder(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // initialize the result
        vector > result;
       
        if (!root)
            return result;
       
        queue my_queue;
       
        my_queue.push(root);
        // push a dummy node into the queue
        my_queue.push(NULL);
       
        // initialize a tmp array
        vector tmp;
       
        while (!my_queue.empty())
        {
            TreeNode *front = my_queue.front();
           
            if (!front)
            {
                // process a dummy
                if (tmp.size() > 0)
                    result.push_back(tmp);
                tmp.erase(tmp.begin(), tmp.end());
                my_queue.pop();
                continue;
            }
            else
            {
                tmp.push_back(front->val);
                my_queue.pop();
            }
           
            if (front->left) my_queue.push(front->left);
            if (front->right) my_queue.push(front->right);
           
            // check if the next node is dummy
            front = my_queue.front();
            if (!front)
            {
                // initialize another dummy into the queue
                my_queue.push(NULL);
            }
        }
       
        return result;
    }
};

[leetcode] binary tree inorder traversal

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector inorderTraversal(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        stack my_stack;
        TreeNode *p = root;
        vector result;
       
        if (!p)
            return result;
           
        while (p)
        {
            my_stack.push(p);
            p = p->left;
        }
       
        while (!my_stack.empty())
        {  
            TreeNode *top = my_stack.top();
            my_stack.pop();
            result.push_back(top->val);

            p = top->right;
           
            while (p)
            {
                my_stack.push(p);
                p = p->left;
            }
        }
       
        return result;
    }
};