[Leetcode] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Analysis:

The idea is pretty straightforward: count the length of list A and B, and move the longer list few steps from its head so that two list are at the same position to the end of the list. Move both lists toward the end of the lists and whenever they met, the node is the first node the intersection begins.

     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int l1 = 0;
        ListNode* p1 = headA;
        while(p1 != NULL) {
            l1++;
            p1 = p1->next;
        }
        
        int l2= 0;
        ListNode* p2 = headB;
        while(p2 != NULL) {
            l2++;
            p2 = p2->next;
        }
        
        p1 = headA;
        p2 = headB;
        if (l1 > l2) {
            for(int i=0; i<l1-l2; i++)
                p1 = p1->next;
        }
        else {
            for(int i=0; i<l2-l1; i++)
                p2 = p2->next;            
        }
        
        while(p1 != NULL && p2 != NULL && p1 != p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
            
        return p1;
    }

[Leetcode] Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Analysis:

Similar to Find Minimum in Rotated Sorted Array, except that you need to take care of duplicate one.

int findMin(vector &num) {
        int b = 0;
        int e = num.size()-1;
        int minVal = num[0];
        while(b <= e)
        {
            int m = (b+e)/2;
            if (num[m] > num[b])
            {
                minVal = min(minVal, num[b]);
                b = m + 1;
            }
            else if (num[m] < num[e])
            {
                minVal = min(minVal, num[m]);
                e = m - 1;
            }
            else if (num[m] == num[e])
            {
                minVal = min(minVal, num[m]);
                e--;
            }
            else if (num[m] == num[b])
            {
                minVal = min(minVal, num[m]);
                b++;
            }
        }
        return minVal;        
    }

[Leetcode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis:

Since it is sorted array, binary search may be the hint. Let m be the middle index of array num, if num[0] < num[m], then first part is sorted, the minimum element would be either num[0] or the minimum of the second part, which can be computed recursively. Similarly, if num[m] < num[n], second part is sorted, the minimum element would be either num[m] or the minimum of the first part. 

 int findMin(vector<int> &num) {
        int b = 0;
        int e = num.size() - 1;
        int minValue = INT_MAX;
        while(b <= e) {
            int m = b + (e- b)/2;
            //it is sorted from b to m
            if (num[b] <= num[m]) {
                minValue = min(num[b], minValue);
                b = m + 1;
            }
            else {
                minValue = min(num[m], minValue);
                e = m-1;
            }
        }
        return minValue;
    }

[Leetcode] Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Analysis:

Apparently, we need to use extra space to store the minimum element of the stack. We can use one stack s to store the pushed element and another stack sMin to store minimum elements appearing so far. Whenever an element x is pushed, if it is less than current minimum (at the top of sMin stack), push x to the sMin; otherwise, the top of the sMin is the minimum and we push it to sMin;

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x < sMin.top())
            sMin.push(x);
        else
            sMin.push(sMin.top());
    }

    void pop() {
        s.pop();
        sMin.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

However, it could not pass Leetcode oj as Memory Limit Exceeded.  By looking at the solution again, we notice that if x is greater than minimum value, there is no need to push the sMin top value. Just do some special handle when popping the element: if the element is greater than minimum, do not pop sMin.

class MinStack {
    stack<int> s;
    stack<int> sMin;
public:
    void push(int x) {
        s.push(x);
        if (sMin.empty() || x <= sMin.top())
            sMin.push(x);
    }

    void pop() {
        if (s.top() <= sMin.top())
            sMin.pop();
        s.pop();
    }

    int top() {
        return s.top();
    }

    int getMin() {
        return sMin.top();
    }
};

In addition, we notice that if all the pushed elements are the same, there are still spaces wasted. It is possible to have a better solution so that few spaces needed for sMin.

[Leetcode] Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

    string addBinary(string a, string b) {
        string ret;
        int i = a.size() - 1;
        int j = b.size() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0 || carry > 0)
        {
            int da = i < a.size() ? a[i] - '0' : 0;
            int db = j < b.size() ? b[j] - '0': 0;
            //the value
            int d = (da + db + carry) % 2;
            //the carry
            carry = (da + db + carry) / 2;
            ret.insert(ret.begin(),1, d + '0');
            i--;
            j--;
        }
        
        return ret;
    }

[Leetcode] Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

vector<int> plusOne(vector<int> &digits) {
        
        int carry = 0;
        vector<int> nums;
        for(int i=digits.size()-1; i >=0; i--)
        {
            int one = i == digits.size()-1 ? 1 : 0;
            int d = (digits[i] + one + carry) % 10;
            carry =  (digits[i] + one + carry) / 10;
            nums.insert(nums.begin(), d);
        }
        //don't forget carry for case {9}
        if (carry > 0)
            nums.insert(nums.begin(), 1);
        
        return nums;
    }

[Leetcode] Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

<pre class="prettyprint linenums:1"><code class="language-cpp"> int sqrt(int x) { int b = 0; int e = x/2 + 1; while(b <= e) { long long mid= (b+e)/2; long long sl = mid * mid; long long sh = (mid+1) * (mid+1); if (sl <= x && sh > x) return mid; else if (sl < x) b = mid + 1; else e = mid - 1; } return -1; } </code></pre>

[Leetcode] Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

int climbStairs(int n) {
        vector<int> f(n+1,0);
        for(int i=0; i<=n; i++)
        {
            if (i == 0)
                f[i] = 1;
            else if (i == 1)
                f[i] = 1;
            else
                f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }

[Leetcode] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

vector<string> splitPath(string path)
    {
        vector<string> ret;
        int i=0;
        while(i < path.size())
        {
            while(i < path.size() && path[i] != '/')
                i++;
            int j = i;
            i++;
            while(i < path.size() && path[i] != '/')
                i++;
                
            if (j != path.size())
                ret.push_back(path.substr(j+1, i-(j+1)));
        }
        return ret;
    }

    string simplifyPath(string path) {
        vector<string> paths = splitPath(path);
        stack<string> s;
        for(int i=0; i<paths.size(); i++)
        {
            //case: "/.."
            if (paths[i] == "..")
            {
                if (!s.empty())
                    s.pop();
            }
            //case: "////"
            else if (paths[i] != "." && paths[i].size() > 0)
                s.push(paths[i]);
        }
        
        string outPath;
        while(!s.empty())
        {
            string p = s.top();
            s.pop();
            outPath.insert(0, p);
            outPath.insert(0,"/");
        }
        
        if (outPath.size() == 0)
            outPath = "/";
            
        return outPath;
        
    }

[Leetcode] Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

void setZeroes(vector<vector<int> > &matrix) {
        //borrow first row and first column as the temporary storage to indicate whether this row/col need to be zeroed
        //use two flag to indicate whether first row/col need to be zeroed 
        bool firstRowZero = false;
        bool firstColZero = false;
        for(int i=0; i<matrix.size(); i++)
        {
            for(int j=0; j<matrix[0].size(); j++)
            {
                if (matrix[i][j] == 0)
                {
                    //0 in the first row
                    if (i == 0)
                        firstRowZero = true;
                    if (j == 0)
                        firstColZero = true;
                    //the col j should be zeroed    
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        //begin from 1 because first row/col can be zero only if firstRowZero is true
        for(int i=1; i<matrix.size(); i++)
        {
            if (matrix[i][0] == 0)
            {
                for(int j =0; j<matrix[0].size(); j++)
                    matrix[i][j] = 0;
            }
        }

        for(int i=1; i<matrix[0].size(); i++)
        {
            if (matrix[0][i] == 0)
            {
                for(int j =0; j<matrix.size(); j++)
                    matrix[j][i] = 0;
            }
        }
        
        //zero first row if necessary
        if (firstRowZero)
        {
            for(int i =0; i<matrix[0].size(); i++)
                matrix[0][i] = 0;
        }

        if (firstColZero)
        {
            for(int i =0; i<matrix.size(); i++)
                matrix[i][0] = 0;
        }
    }

[Leetcode] Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

    bool searchMatrix(vector<vector<int> > &matrix, int target) {
        int b = 0;
        int e = matrix.size() * matrix[0].size() - 1;
        while(b <= e)
        {
            //treat the whole matrix as a long array and do the binary search
            int m = (b+e)/2;
            int row = m / matrix[0].size();
            int col = m % matrix[0].size();
            if (matrix[row][col] == target)
                return true;
            else if (target < matrix[row][col])
                e = m - 1;
            else
                b = m + 1;
        }
        
        return false;
    }

[Leetcode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

    void sortColors(int A[], int n) {
        int i = 0;
        int j = 0;
        int k = n-1;
        while(i <= k)
        {
            if (A[i] == 0)
            {
                //swap 0 with the first 1 so that all 0s are before 1s
                swap(A[i], A[j]);
                i++;
                j++;
            }
            else if (A[i] == 1)
            {
                //do nothing if it is 1
                i++;
            }
            else
            {
                //swap 2 with the last element which is not 2
                //note A[k] could be 2 as well so we should not move i forward
                swap(A[i], A[k]);
                k--;
            }
        }
    }

[Leetcode] Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

void dfs(vector<vector<int> >& ret, int n, int k, int m, vector<int>& nums)
{
 if (nums.size() == k)
 {
  ret.push_back(nums);
 }
 else
 {
  for (int i = m; i <= n; i++)
  {
   nums.push_back(i);
   dfs(ret, n, k, i + 1, nums);
   nums.pop_back();
  }
 }
}

vector<vector<int> > combine(int n, int k) {
 vector<vector<int> > ret;
 vector<int> nums;
 dfs(ret, n, k, 1, nums);

 return ret;
}

[Leetcode] Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

void helper(vector<int> S, vector<vector<int> >& ret, vector<int>& tmp, int k)
    {
        ret.push_back(tmp);
        for(int i=k; i<S.size(); i++)
        {
            tmp.push_back(S[i]);
            helper(S, ret, tmp, i+1);
            tmp.pop_back();
        }
    }

    vector<vector<int> > subsets(vector<int> &S) {
        sort(S.begin(), S.end());
        vector<vector<int> > ret;
        vector<int> tmp;
        helper(S, ret, tmp, 0);
        
        return ret;
    }

[Leetcode] Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

    bool helper(vector<vector<char> > &board, string word, int i, int j, int k)
    {
        //if all char in the word has been found in the board
        if (k == word.size())
            return true;
        //if not the correct way    
        else if (i <0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] == '#' || word[k] != board[i][j])
            return false;
        else 
        {
            char tmp = board[i][j];
            board[i][j] = '#';
            //if andy of all its neighbors matches, we found a solution
            if (helper(board, word, i +1, j, k+1) ||
                helper(board, word, i, j+1, k+1) ||
                helper(board, word, i-1, j, k+1) ||
                helper(board, word, i, j-1, k+1))
                return true;
            //otherwise, backtrack
            board[i][j] = tmp;
            
            return false;            
        }

    }

    bool exist(vector<vector<char> > &board, string word) {
        for(int i=0; i<board.size(); i++)
        {
            for(int j=0; j<board[0].size(); j++)
            {
                //find a char in the board match the first char of the word
                if (board[i][j] == word[0])
                {
                    if (helper(board, word, i, j, 0))
                        return true;
                }
            }
        }
        
        return false;
    }

[leetcode] Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

    int removeDuplicates(int A[], int n) {
        if (n <= 2)
            return n;
        int j = 1;
        int count = 1;
        for(int i=1; i<n; i++)
        {
            //copy to the dest if current element is equal to previous element and count <= 2
            if (A[i] == A[i-1] && count < 2)
            {
                A[j++] = A[i];
                count++;
            }
            //or current element is not equal to previous element 
            else if (A[i] != A[i-1])
            {
                A[j++] = A[i];
                count = 1;
            }
        }
        
        return j;
    }

[Leetcode] Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

    bool search(int A[], int n, int target) {
        int b = 0;
        int e = n - 1;
        while(b <= e)
        {
            int m = (b + e) / 2;
            if (A[m] == target)
                return true;
   //right part duplicate, and move end backward as the end value could not be the target 
            else if (A[m] == A[e])
                e = e - 1;
   //left part duplicate, and move begin forward as the begin value could not be the target  
            else if (A[m] == A[b])
                b = b + 1;
   //if the right part is still sorted 
            else if (A[m] < A[e])
            {
    //if the target is in the right side range
                if (target > A[m] && target <= A[e])
                    b = m + 1;
                else
                    e = m - 1;
            }
   //left part must be sorted 
            else
            {
    //if the target is in the left side range
                if (target < A[m] && target >= A[b])
                    e = m - 1;
                else
                    b = m + 1;                
            }
        }
        
        return false;
    }

[leetcode] Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

ListNode *deleteDuplicates(ListNode *head) {
        ListNode* curr = head;
        while(curr != NULL && curr->next != NULL)
        {
   //if curr node value is equal to the next node value, remove the next node
            if (curr->val == curr->next->val)
            {
                ListNode* tmp = curr->next;
                curr->next = curr->next->next;
                delete tmp;
            }
            else
            {
    //otherwise, move to next node
                curr = curr->next;
            }
        }
        return head;
    }

[Leetcode] Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
  //use dummy head to make it easy to handle head node which is duplicate
        ListNode* prev = dummyHead;
        ListNode* curr = head;
        while(curr != NULL)
        {
   //When find a node whose value is equal to its next node
            if (curr->next != NULL && curr->val == curr->next->val)
            {
    //remove all its next nodes
                while(curr != NULL && curr->next != NULL && curr->val == curr->next->val)
                {
                    ListNode* next = curr->next;
                    curr->next = curr->next->next;
                    delete next;
                }
    //then remove itself. 
                ListNode* tmp = curr;
                prev->next = curr->next;
                curr = curr->next;
                delete tmp;
            }
            else
            {
    //otherwise, move to next node
                prev = curr;
                curr = curr->next;
            }
        }
        
        return dummyHead->next;
    }
};

[Leetcode] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Analysis:

• Create left part of list for nodes less than x
• create right part of list for nodes greater than or equal to x
• concatenate them

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode* dummyHead1 = new ListNode(0);
        ListNode* dummyHead2 = new ListNode(0);
        ListNode* p1 = dummyHead1;
        ListNode* p2 = dummyHead2;
        while(head != NULL)
        {
            if (head->val < x)
            {
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2 = p2->next;
            }
            head = head->next;
        }
        
        p2->next = NULL;
        p1->next = dummyHead2->next;
        
        return dummyHead1->next;
    }
};

[Leetcode] Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Analysis:

for "rgtae" and "great", compare the following Recursively

r|gtae, g|reat, r|gtae, grea|t, 

Rg|tae, gr|eat, rg|tae, gre|at, 

rgt|ae, gre|at, rgt|ae, gr|eat, 

Rgta|e, grea|t, rgta|e, g|reat 

    bool isScramble(string s1, string s2) {
            if (s1.size() != s2.size())
                return false;
            else if (s1 == s2)
                return true;
            else
            {
                unordered_map<char, int> m;
                for (int i=0; i<s1.size(); i++)
                    m[s1[i]]++;
                for (int i=0; i<s2.size(); i++)
                {
                    if (m.find(s2[i]) == m.end() || m[s2[i]] <= 0)
                        return false;
                    m[s2[i]]--;
        
                }
                
                for(int i=1; i<s1.size();i++)
                {
                    if ((isScramble(s1.substr(0,i),s2.substr(0,i)) && isScramble(s1.substr(i),s2.substr(i))) || 
                        (isScramble(s1.substr(0,i),s2.substr(s1.size() - i)) && isScramble(s1.substr(i),s2.substr(0,s1.size() - i))))
                        return true;
                }
                return false;                
            }
    }

[Leetcode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = m -1;
        int j = n - 1;
        while(i >=0 && j >=0)
        {
            if (A[i] > B[j])
                A[i+j+1] = A[i--];
            else
                A[i+j+1] = B[j--];
        }
        
        while(j >=0)
        {
            A[i+j+1] = B[j--];
        }
    }
};

[Leetcode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Analysis:

    vector<int> grayCode(int n) {
  
        vector<int> codes(1,0);
        for (int i = 0; i<n; i++)
        {
            for (int j=codes.size()-1; j >=0 ; j--)
            {
                int code = 0x1 << i | codes[j];
                codes.push_back(code);
            }
        }
        
        return codes;
    }

[Leetcode] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

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

Analysis:

class Solution {
public:

    bool helper(TreeNode *root, int minVal, int maxVal) {
        if (root == NULL)
            return true;
        else
            return root->val < maxVal && 
            root->val > minVal &&
            helper(root->left, minVal, root->val) &&
            helper(root->right, root->val, maxVal);
        
    }

    bool isValidBST(TreeNode *root) {
        return helper(root, INT_MIN, INT_MAX);
    }
};

[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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

Analysis:

For BST, the inorder traversal will get the list of elements in sorted order. If two elements were swapped, there are two cases, the elements are next to each other or not. 

1,  2,  5,  4,  3,  6

         ^p1     ^p2

1,  2,  4,  3,  5,  6

          ^p1^p2

Doing an inorder traversal and the elements are marked as p1 and p2 if current element is less than previous element.   

class Solution {
public:

    void helper(TreeNode *root, TreeNode* &prev, TreeNode* &p1, TreeNode* &p2) {
        if (root == NULL)
            return;
        
        helper(root->left, prev, p1, p2);
            
        if (prev != NULL && root->val < prev->val)
        {
            if (p1 == NULL)
            {
                p1 = prev;
                p2 = root;
            }
            else
            {
                p2 = root;
            }
        }
        
        prev = root;
        
        helper(root->right, prev, p1, p2);
    }

    void recoverTree(TreeNode *root) {
        TreeNode *prev = NULL;
        TreeNode *p1 = NULL;
        TreeNode *p2 = NULL;
        
        helper(root, prev, p1, p2);
        
        swap(p1->val, p2->val);
    }
};

[Leetcode] Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Analysis:

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if (p == NULL && q == NULL)
            return true;
        else if (p == NULL || q == NULL)
            return false;
        else
        {
            return p->val == q->val && 
            isSameTree(p->left, q->left) &&
            isSameTree(p->right, q->right);
        }
    }
};

[Leetcode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

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

Analysis:

class Solution {
public:

    bool helper(TreeNode *left, TreeNode* right) {
        if (left == NULL && right == NULL)
            return true;
        else if (left == NULL || right == NULL)
            return false;
        else
        {
            return left->val == right->val 
            && helper(left->left, right->right)
            && helper(left->right, right->left);
        }
    }
    bool isSymmetric(TreeNode *root) {
        if (root == NULL)
            return true;
        else
            return helper(root->left, root->right);
    }
};

[Leetcode] 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.

Analysis:

class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            row.push_back(t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                currLevel = nextLevel;
                nextLevel = 0;
                ret.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};

[Leetcode] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

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

Analysis:

class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        vector<vector<int> > ret;
        if (root == NULL)
            return ret;
        queue<TreeNode*> q;
        int currLevel = 1;
        int nextLevel = 0;
        q.push(root);
        vector<int> row;
        int level = 1;
        while(!q.empty())
        {
            TreeNode* t = q.front();
            q.pop();
            currLevel--;
            if (level % 2 == 1)
                row.push_back(t->val);
            else
                row.insert(row.begin(), t->val);
            if (t->left != NULL)
            {
                q.push(t->left);
                nextLevel++;
            }
            if (t->right != NULL)
            {
                q.push(t->right);
                nextLevel++;
            }                
            
            if (currLevel == 0)
            {
                level++;
                currLevel = nextLevel;
                nextLevel = 0;
                ret.push_back(row);
                row.clear();
            }
        }
        
        return ret;        
    }
};