public class Solution {
public int maxProduct(int[] A) {
List B = new ArrayList();
for(int i = A.length - 1; i >= 0; --i) {
B.add(A[i]);
}
int[] BB = new int[A.length];
for(int i = 0; i < A.length; ++i) {
BB[i] = B.get(i);
}
return Math.max(maxProductHelper(A), maxProductHelper(BB));
}
public int maxProductHelper(int[] A) {
int currentMax = A[0];
int product = A[0];
int grandproduct = A[0];
for(int i = 1; i < A.length; ++i) {
grandproduct *= A[i];
if(A[i] == 0) {
currentMax = Math.max(currentMax, 0);
currentMax = Math.max(currentMax, product);
product = 0;
grandproduct = 1;
} else if(A[i] < 0) {
currentMax = Math.max(currentMax, product);
if(grandproduct > 0) {
product = grandproduct;
currentMax = Math.max(currentMax, product);
}
else if (grandproduct == 0) {
grandproduct = A[i];
product = A[i];
} else {
product = 0;
}
} else {
if(grandproduct == 0) {
grandproduct = A[i];
}
if(product == 0) {
product = 1;
}
product *= A[i];
currentMax = Math.max(currentMax, product);
}
}
return currentMax;
}
}
10/02/2014
Leetcode -- Maximum Product Subarray
Made a really complicated and ugly solution, will refactor later:
6/15/2014
Evaluate Math Expression
A hacky way with python is quite simple
print eval('1+ 2*3 - 5', {'__builtins__' : None})
Otherwise, we assume there is not brackets
print eval('1+ 2*3 - 5', {'__builtins__' : None})
Otherwise, we assume there is not brackets
#include <iostream>
#include <stack>
using namespace std;
class Eval {
public:
int operator()(string s) {
stack<int> operands;
stack<char> operators;
int num = 0;
for(int i = 0; i < s.length(); ++i) {
if(s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
} else if(s[i] == '+' || s[i] == '-') {
if(operands.empty()) {
operands.push(num);
} else {
if(!operators.empty() && (operators.top() == '*' || operators.top()=='/')) {
if(operators.top() == '*') {
operands.top() *= num;
} else if(operators.top() == '/') {
operands.top() /= num;
}
operators.pop();
}
}
operators.push(s[i]);
num = 0;
} else if(s[i] == '*' || s[i] == '/') {
operands.push(num);
operators.push(s[i]);
num = 0;
}
}
operands.push(num);
while(operands.size() > 1) {
int right = operands.top();
operands.pop();
int left = operands.top();
operands.pop();
char op = operators.top();
operators.pop();
if(op=='+') {
left += right;
} else if(op=='-') {
left -= right;
} else if(op=='*') {
left *= right;
} else if (op=='/') {
left /= right;
}
operands.push(left);
}
return operands.top();
}
};
int main(int argc, char *argv[])
{
Eval eval;
std::cout << eval("1+2*3 + 5 * 10") << std::endl;
return 0;
}
6/08/2014
Leetcode -- Interleaving String
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();
int n2 = s2.size();
int n3 = s3.size();
if(n1 + n2 != n3) {
return false;
}
vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, 0));
dp[0][0] = 1;
for(int i = 1; i <=n1; ++i) {
if(s1[i - 1] == s3[i - 1] && dp[i - 1][0]) {
dp[i][0] = 1;
}
}
for(int j = 1; j <= n2; ++j) {
if(s2[j - 1] == s3[j - 1] && dp[0][j - 1]) {
dp[0][j] = 1;
}
}
for(int i = 1; i <= n1; ++i) {
for(int j = 1; j <= n2; ++j) {
dp[i][j] = dp[i - 1][j] && s1[i - 1] == s3[i + j - 1] || dp[i][j - 1] && s2[j - 1] == s3[i + j - 1];
}
}
return dp[n1][n2];
}
};
Leetcode -- Recover Binary Search Tree
/**
* 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 recoverTree(TreeNode *root) {
TreeNode * n1 = NULL;
TreeNode * n2 = NULL;
TreeNode * prev = NULL;
recoverTree(root, n1, n2, prev);
if(n1 && n2) {
int temp = n1->val;
n1->val = n2->val;
n2->val = temp;
}
}
void recoverTree(TreeNode * root, TreeNode *& n1, TreeNode *& n2, TreeNode *& prev) {
if(!root) {
return;
}
recoverTree(root->left, n1, n2, prev );
if(prev && prev->val > root->val) {
n2 = root;
if(!n1) {
n1 = prev;
}
}
prev = root;
recoverTree(root->right, n1, n2, prev );
}
};
6/07/2014
Leetcode -- Convert Sorted List to Binary Search Tree
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
if(head == NULL) {
return NULL;
}
// check the length of the list node
ListNode * p = head;
int length = 0;
while(p != NULL) {
length++;
p = p->next;
}
return sortedListToBST(head, 0, length - 1);
}
TreeNode * sortedListToBST(ListNode *& head, int start, int end) {
if(start > end) {
return NULL;
}
int mid = start + (end - start) / 2;
TreeNode * left = sortedListToBST(head, start, mid - 1);
TreeNode * parent = new TreeNode(head->val);
parent->left = left;
head = head->next;
parent->right = sortedListToBST(head, mid + 1, end);
return parent;
}
};
6/03/2014
Leetcode -- Surrounding Regions
Basically just copied from Internet.
class Solution {
public:
void solve(vector<vector<char>> &board) {
if(board.empty()) {
return;
}
vector<int> xIndex;
vector<int> yIndex;
int row = board.size();
int column = board[0].size();
for(int i = 0; i < row; ++i) {
if(board[i][0] == 'O') {
xIndex.push_back(i);
yIndex.push_back(0);
}
if(board[i][column - 1] == 'O') {
xIndex.push_back(i);
yIndex.push_back(column - 1);
}
}
for(int i = 1; i < column; ++i) {
if(board[0][i] == 'O') {
xIndex.push_back(0);
yIndex.push_back(i);
}
if(board[row - 1][i] == 'O') {
xIndex.push_back(row - 1);
yIndex.push_back(i);
}
}
int k = 0;
for(int i = 0; i < xIndex.size(); ++i) {
int x = xIndex[i];
int y = yIndex[i];
board[x][y] = 'Y';
if(x > 0 && board[x-1][y] == 'O') {
xIndex.push_back(x-1);
yIndex.push_back(y);
}
if(x < row - 1 && board[x+1][y] == 'O') {
xIndex.push_back(x + 1);
yIndex.push_back(y);
}
if(y > 0 && board[x][y - 1] == 'O') {
xIndex.push_back(x);
yIndex.push_back(y- 1);
}
if(y < column - 1 && board[x][y + 1] == 'O') {
xIndex.push_back(x);
yIndex.push_back(y+ 1);
}
}
for(int i = 0; i < row; ++i) {
for(int j = 0; j < column; ++j) {
if(board[i][j] == 'Y') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}
};
6/01/2014
Leetcode -- Candy
Scan from both beginning and back, catch the strictly increasing and strictly decreasing ratings. When do the backward scan, be careful that if the current candy at location j is already greater than the expected candy, do not change it.
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int candy(vector<int> &ratings) {
int last = 0;
vector<int> candies(ratings.size(), 1);
for(int i = 1; i < ratings.size(); ++i) {
if(ratings[i] <= ratings[i - 1]) {
int num = 1;
for(int j = last; j < i; ++j) {
candies[j] = num++;
}
last = i;
}
}
int num = 1;
for(int j = last; j < ratings.size(); ++j) {
candies[j] = num++;
}
last = ratings.size() - 1;
for(int i = ratings.size() - 2; i >= 0; --i) {
if(ratings[i] <= ratings[i+ 1]) {
int num = 1;
for(int j = last; j > i; --j) {
candies[j] = candies[j] > num ? candies[j] : num++;
}
last = i;
}
}
num = 1;
for(int j = last; j >=0; --j) {
candies[j] = candies[j] > num ? candies[j] : num++;
}
int sum = 0;
for(int i = 0; i < candies.size(); ++i) {
sum+= candies[i];
}
return sum;
}
};
int main(int argc, char *argv[])
{
Solution s;
vector<int> ratings{2,2,1};
std::cout << s.candy(ratings) << std::endl;
return 0;
}
5/26/2014
Leetcode - Word Ladder
class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
// BFS
queue<string> q;
q.push(start);
dict.erase(start);
int length = 1;
while(!q.empty()) {
queue<string> tempQ;
while(!q.empty()) {
string str(q.front());
q.pop();
set<string> ret(getOneEditedWord(str, dict));
for(string s : ret) {
if(s == end) {
return length + 1;
}
tempQ.push(s);
}
}
length++;
swap(q, tempQ);
}
return 0;
}
set<string> getOneEditedWord(string str, unordered_set<string> & dict) {
set<string> result;
for(int i = 0; i < str.length(); ++i) {
for(int j = 'a'; j <='z'; ++j) {
if(j == str[i]) {
continue;
}
char temp = str[i];
str[i] = j;
if(dict.count(str) > 0) {
result.insert(str);
dict.erase(str);
}
str[i] = temp;
}
}
return result;
}
};
Heap and maintain the median
Here the classic approach to handle a heap is insert new element at the root and sift it down.
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
#include <stdlib.h>
#include <memory>
#include <time.h>
#include <set>
using namespace std;
template <typename T>
class Heap {
vector<T> _heap;
public:
// never call a virtual function from constructor
void build(const vector<T>& nums) {
for(int i = 0; i < nums.size(); ++i) {
offer(nums[i]);
}
}
T peek() const {
if(!_heap.empty()) {
return _heap[0];
} else {
std::cerr << "heap is empty" << std::endl;
}
}
void offer(T val) { //insert
_heap.insert(_heap.begin(), val);
heapify();
}
T poll() { // delete
int val = _heap[0];
swap(0, _heap.size() - 1);
_heap.pop_back();
heapify();
return val;
}
void print() {
for_each(_heap.begin(), _heap.end(), [](T val) {
std::cout << val << ", ";
});
std::cout << std::endl;
}
int size() const {
return _heap.size();
}
virtual ~ Heap() {}
private:
void heapify() {
heapify(0);
}
void heapify(int i) {
//sift down
int l = left(i);
int r = right(i);
int largest = i;
if(l < _heap.size() && comp(_heap[l], _heap[largest])) {
largest = l;
}
if(r < _heap.size() && comp(_heap[r], _heap[largest])) {
largest = r;
}
if (largest != i) {
swap(largest, i);
heapify(largest);
}
}
inline void swap(int i, int j) {
if(i >= _heap.size() && j >= _heap.size()) {
throw std::runtime_error("Out of bound!");
}
int temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
inline int parent(int i) {
return i / 2;
}
inline int left(int i) {
return 2 * i;
}
inline int right(int i) {
return 2 * i + 1;
}
virtual bool comp(T val1, T val2) const = 0;
};
template<typename T>
class MaxHeap : public Heap<T> {
public:
virtual ~MaxHeap() {}
private:
virtual bool comp(T val1, T val2) const {
return val1 > val2;
}
};
template <typename T>
class MinHeap : public Heap<T> {
public:
virtual ~MinHeap() {}
private:
virtual bool comp(T val1, T val2) const {
return val1 < val2;
}
};
class StreamMediam {
private:
MinHeap<int> _minHeap;
MaxHeap<int> _maxHeap;
set<int> _record;
public:
StreamMediam() {
srand (time(NULL));
}
int genRandNum(int maxNum) {
return rand() % maxNum;
}
void accept(int maxNum = 100) {
int val = genRandNum(maxNum);
_record.insert(val);
if(_minHeap.size() == _maxHeap.size()) {
if(_minHeap.size() > 0 && val > _minHeap.peek()) {
_maxHeap.offer(_minHeap.poll());
_minHeap.offer(val);
} else {
_maxHeap.offer(val);
}
} else {
if(val < _maxHeap.peek()) {
_minHeap.offer(_maxHeap.poll());
_maxHeap.offer(val);
} else {
_minHeap.offer(val);
}
}
}
int getMedian() const {
if(_minHeap.size() == _maxHeap.size()) {
return (_minHeap.peek() + _maxHeap.peek() ) / 2;
} else {
return _maxHeap.peek();
}
}
void print() {
for_each(_record.begin(), _record.end(), [](int val) {
std::cout << val << ", ";
});
std::cout << std::endl;
}
};
int main(int argc, char *argv[])
{
vector<int> nums{4,1,3,2,16,9,10,14,8,7};
shared_ptr<Heap<int> > heap1(new MaxHeap<int>());
heap1->build(nums);
heap1->print();
shared_ptr<Heap<int> > heap2(new MinHeap<int>());
heap2->build(nums);
heap2->print();
StreamMediam sm;
for(int i = 0; i < 10; ++i) {
sm.accept();
sm.print();
std::cout << sm.getMedian() << std::endl;
}
return 0;
}
5/18/2014
Leetcode -- Merge Two Sorted Array
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
while(m >= 1 && n >= 1) {
if(A[m - 1] > B[n - 1]) {
A[m + n - 1] = A[m - 1];
m--;
} else {
A[m + n - 1] = B[n - 1];
n--;
}
}
while(n>=1) {
A[n - 1] = B[n - 1];
n--;
}
}
};
Leetcode -- LRU Cache
class LRUCache{
public:
list<vector<int> > _list;
unordered_map<int, list<vector<int> >::iterator> _hash;
int _capacity;
LRUCache(int capacity): _capacity(capacity) {
}
int get(int key) {
if(_hash.count(key) > 0) {
auto it = _hash[key];
vector<int> temp(*it);
_list.erase(it);
_list.push_front(temp);
_hash[key] = _list.begin();
return temp[1];
} else {
return -1;
}
}
void set(int key, int value) {
if(_hash.count(key) > 0) {
auto it = _hash[key];
_list.erase(it);
_list.push_front(vector<int>{key, value});
_hash[key] = _list.begin();
} else {
if(_hash.size() >= _capacity) {
vector<int> temp(_list.back());
_list.pop_back();
_hash.erase(temp[0]);
}
vector<int> newElement{key, value};
_list.push_front(newElement);
_hash.emplace(key, _list.begin());
}
}
};
5/13/2014
Unique Path
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[1000] = {-1};
dp[0] = 1;
for(int i = 0; i < m; ++i) {
for(int j = 1; j < n; ++j) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
};
4/27/2014
Leetcode -- Minimum Window Substring
#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;
class Solution {
public:
string minWindow(string S, string T) {
if(S.empty()) {
return "";
}
unordered_map<char, int> expectedToFind;
unordered_map<char, int> hasFound;
for(int i = 0; i < T.length(); ++i) {
expectedToFind[T[i]]++;
}
int minLength = INT_MAX;
int minStart = 0;
int minEnd = 0;
int count = 0;
for(int start = 0, end = 0; end < S.length(); end++) {
if(expectedToFind[S[end]] > 0) {
hasFound[S[end]]++;
}
if(expectedToFind[S[end]] > 0 && hasFound[S[end]] <= expectedToFind[S[end]]) {
count++;
}
if(count == T.length()) {
while(expectedToFind[S[start]] == 0 || hasFound[S[start]] > expectedToFind[S[start]]) {
if(hasFound[S[start]] > expectedToFind[S[start]] ) {
hasFound[S[start]]--;
}
start++;
}
int wLen = end - start + 1;
if(wLen < minLength) {
minLength = wLen;
minStart = start;
minEnd = end;
}
}
}
return count == T.length() ? S.substr(minStart, minEnd - minStart + 1): "";
}
};
int main(int argc, char *argv[])
{
Solution s;
std::cout << s.minWindow("a", "a") << std::endl;
return 0;
}
4/26/2014
Leetcode -- Word Break II
TLE because I didn't use dynamic programming
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> breaks;
string output;
wordBreakHelper(s, 0, dict, output, breaks);
return breaks;
}
void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks) {
if(start >= s.length()) {
breaks.emplace_back(output.substr(1));
return;
}
for(int i = start; i < s.length(); ++i) {
string sub(s.substr(start, i - start + 1));
if(dict.count(sub) > 0) {
output +=" " + sub;
wordBreakHelper(s, i + 1, dict, output, breaks);
output = output.substr(0, output.length() - 1-sub.length());
}
}
}
};
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
vector<string> breaks;
string output;
vector<bool> possible(s.length() + 1, true);
wordBreakHelper(s, 0, dict, output, breaks, possible);
return breaks;
}
void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks, vector<bool>& possible) {
if(start >= s.length()) {
breaks.emplace_back(output.substr(1));
return;
}
for(int i = start; i < s.length(); ++i) {
string sub(s.substr(start, i - start + 1));
if(dict.count(sub) > 0 && possible[i + 1]) {
output +=" " + sub;
int beforeTheChange = breaks.size();
wordBreakHelper(s, i + 1, dict, output, breaks, possible);
if(beforeTheChange == breaks.size()) {
possible[i + 1] = false;
}
output = output.substr(0, output.length() - 1-sub.length());
}
}
}
};
4/23/2014
Leetcode -- Sort List
Seems the easiest way is to use merge sort
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
if(head == NULL || head->next == NULL) {
return head;
}
ListNode * slower = head;
ListNode * faster = head->next;
while(faster != NULL && faster->next != NULL) {
slower = slower->next;
faster = faster->next;
faster = faster->next;
}
ListNode * temp = slower->next;
slower->next = NULL;
ListNode * left = sortList(head);
ListNode * right = sortList(temp);
return mergeList(left, right);
}
ListNode * mergeList(ListNode * head1, ListNode * head2) {
ListNode * dummy = new ListNode(-1);
ListNode * p = dummy;
while(head1 != NULL || head2 != NULL) {
if(head1 != NULL && head2 != NULL) {
if(head1->val < head2->val) {
p->next = head1;
head1 = head1->next;
} else {
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if(head1 != NULL && head2 == NULL) {
p->next = head1;
break;
}
if(head2 != NULL && head1 == NULL) {
p->next = head2;
break;
}
}
return dummy->next;
}
};
4/22/2014
Leetcode -- Unique Paths II
Took some tuning work to get this right, essentially, dp + recursion
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int> > cache(m, vector<int>(n, -1));
bool isObstacle = false;
for(int i = 0; i < m ; ++i) {
if(obstacleGrid[i][0]) {
isObstacle = true;
}
cache[i][0] = !isObstacle;
}
isObstacle = false;
for(int i = 0; i < n ; ++i) {
if(obstacleGrid[0][i]) {
isObstacle = true;
}
cache[0][i] = !isObstacle;
}
cache[0][0] = !obstacleGrid[0][0];
uniquePathsWithObstaclesHelper(m - 1, n - 1, obstacleGrid, cache);
return cache[m - 1][n - 1];
}
int uniquePathsWithObstaclesHelper(int m, int n, vector<vector<int> >& obstacleGrid, vector<vector<int> >& cache) {
if(m < 0 || n < 0) {
return 0;
}
if(m == 0 || n == 0) {
return cache[m][n];
}
if(obstacleGrid[m][n]) {
cache[m][n] = 0;
return 0;
}
int left = cache[m][n - 1] == -1 ? uniquePathsWithObstaclesHelper(m, n - 1, obstacleGrid, cache) : cache[m][n - 1];
int up = cache[m - 1][n] ? uniquePathsWithObstaclesHelper(m - 1, n, obstacleGrid, cache) : cache[m - 1][n];
cache[m][n] = left + up;
return cache[m][n];
}
};
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
int dp[1000] = {-1};
dp[0] = !obstacleGrid[0][0];
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(j == 0) {
dp[j] = obstacleGrid[i][j] ? 0 : dp[j];
continue;
}
dp[j] = obstacleGrid[i][j] ? 0 : dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
};
Leetcode -- Clone Graph
This is a simple question. Just use a map to log whether the node was copied. I made a mistake by putting hash.emplace(node, clonedNode); after the for loop, this will cause infinite loop.
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> hash;
if(node == NULL) {
return NULL;
}
return cloneGraphHelper(node, hash);
}
UndirectedGraphNode * cloneGraphHelper(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *>& hash) {
if(hash.count(node) > 0) {
return hash[node];
}
UndirectedGraphNode * clonedNode = new UndirectedGraphNode(node->label);
hash.emplace(node, clonedNode); // made mistake here
vector<UndirectedGraphNode *> neighbors;
for(UndirectedGraphNode * neighbor : node->neighbors) {
UndirectedGraphNode * cloneNeighbor = cloneGraphHelper(neighbor, hash);
neighbors.emplace_back(cloneNeighbor);
}
swap(clonedNode->neighbors,neighbors);
return clonedNode;
}
};
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if(node == NULL) {
return NULL;
}
unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> hash;
return cloneGraph(node, hash);
}
UndirectedGraphNode * cloneGraph(UndirectedGraphNode* node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *>& hash) {
if(hash.count(node) > 0) {
return hash[node];
}
UndirectedGraphNode * cloneNode = new UndirectedGraphNode(node->label);
hash.emplace(node, cloneNode);
for(UndirectedGraphNode * neighbor : node->neighbors) {
cloneNode->neighbors.emplace_back(cloneGraph(neighbor, hash));
}
return cloneNode;
}
};
4/21/2014
Leetcode -- Construct Binary Tree from Inorder and Postorder Traversal
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
if(inorder.empty() || postorder.empty()) {
return NULL;
}
return buildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode * buildTree(vector<int>& inorder, int iStart, int iEnd, vector<int>& postorder, int pStart, int pEnd) {
if(iStart > iEnd || pStart > pEnd) {
return NULL;
}
TreeNode * root = new TreeNode (postorder[pEnd]);
int i = iStart;
for(; i <= iEnd; ++i) {
if(inorder[i] == postorder[pEnd]) {
break;
}
}
root->left = buildTree(inorder, iStart, i - 1, postorder, pStart, pStart + i - iStart - 1);
root->right = buildTree(inorder, i + 1, iEnd, postorder, pEnd + i - iEnd, pEnd - 1);
return root;
}
};
4/20/2014
Leetcode -- Binary Tree Level Order Traversal II
Here we use recursion as stack
/**
* 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<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int> > result;
if(root == NULL) {
return result;
}
vector<TreeNode *> output;
output.emplace_back(root);
levelOrderBottomHelper(output, result);
return result;
}
void levelOrderBottomHelper(vector<TreeNode *>& output, vector<vector<int> >& result) {
vector<TreeNode *> nodes;
for(int i = 0; i < output.size(); ++i) {
if(output[i]->left != NULL) {
nodes.emplace_back(output[i]->left);
}
if(output[i]->right != NULL) {
nodes.emplace_back(output[i]->right);
}
}
if(!nodes.empty()) {
levelOrderBottomHelper(nodes, result);
}
vector<int> temp;
for(TreeNode * node : output) {
temp.emplace_back(node->val);
}
result.emplace_back(temp);
}
};
Leetcode -- Flatten Binary Tree to Linked List
/**
* 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) {
flattenHelper(root);
}
TreeNode * flattenHelper(TreeNode * root) {
if(root == NULL) {
return root;
}
TreeNode * leftFlatten = flattenHelper(root->left);
TreeNode * rightFlatten = flattenHelper(root->right);
if(leftFlatten != NULL) {
root->right = leftFlatten;
TreeNode * p = root;
while(p->right != NULL) {
p = p->right;
}
p->right = rightFlatten;
}
root->left = NULL; //DON'T FORGET TO CLEAR LEFT TREE!!!!!
return root;
}
};
Subscribe to:
Posts (Atom)