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