-
第 31 樓 / webdriver
- 時間: 2014-9-23 13:16Now comes the solution (in C++) ...
Recursion...
代碼: /**
* 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 maxPathSum(TreeNode *root) {
int res = INT_MIN;
maxPathSumRe(root, res);
return res;
}
int maxPathSumRe(TreeNode *node, int &res)
{
if (!node) return 0;
int l = maxPathSumRe(node->left, res);
int r = maxPathSumRe(node->right, res);
int sum = max(node->val, max(l, r) + node->val);
res = max(res, sum);
res = max(res, l + r + node->val);
return sum;
}
};
-
-
- 時間: 2014-9-23 13:17
-
-
- 時間: 2014-9-23 13:18Now comes the solution (in C++) ...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
You may refer to my blog for more detailed explanations:
www.cnblogs.com/AnnieK...ersal.html
代碼: /**
* 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<int> postorderTraversal(TreeNode *root) {
return postorderTraversal_1(root);
}
vector<int> postorderTraversal_1(TreeNode *root) {
vector<int> res;
stack<TreeNode *> stk;
TreeNode *last = NULL, *cur = root;
while(cur || !stk.empty()){
if (cur) {
stk.push(cur);
cur = cur->left;
}
else{
TreeNode *peak = stk.top();
if(peak->right && last != peak->right)
cur = peak->right;
else{
res.push_back(peak->val);
stk.pop();
last = peak;
}
}
}
return res;
}
vector<int> postorderTraversal_2(TreeNode *root) {
vector<int> res;
postorderTraversalRe(root, res);
return res;
}
void postorderTraversalRe(TreeNode *node, vector<int> &res) {
if (!node) return;
postorderTraversalRe(node->left, res);
postorderTraversalRe(node->right, res);
res.push_back(node->val);
}
vector<int> postorderTraversal_3(TreeNode *root) {
vector<int> res;
TreeNode dump(0);
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while (cur)
{
if (cur->left == NULL)
{
cur = cur->right;
}
else
{
prev = cur->left;
while (prev->right != NULL && prev->right != cur)
prev = prev->right;
if (prev->right == NULL)
{
prev->right = cur;
cur = cur->left;
}
else
{
printReverse(cur->left, prev, res); // call print
prev->right = NULL;
cur = cur->right;
}
}
}
return res;
}
void printReverse(TreeNode* from, TreeNode *to, vector<int>& res) // print the reversed tree nodes 'from' -> 'to'.
{
reverse(from, to);
TreeNode *p = to;
while (true)
{
res.push_back(p->val);
if (p == from)
break;
p = p->right;
}
reverse(to, from);
}
void reverse(TreeNode *from, TreeNode *to) // reverse the tree nodes 'from' -> 'to'.
{
if (from == to)
return;
TreeNode *x = from, *y = from->right, *z;
while (true)
{
z = y->right;
y->right = x;
x = y;
y = z;
if (x == to)
break;
}
}
}; -
- 時間: 2014-9-23 13:20
-
- 時間: 2014-9-23 13:21Now comes the solution (in C++) ...
1. Iterative way (stack). Time: O(n), Space: O(n).
2. Recursive solution. Time: O(n), Space: O(n).
3. Threaded tree (Morris). Time: O(n), Space: O(1).
代碼: **
* 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<int> preorderTraversal(TreeNode *root) {
return preorderTraversal_3(root);
}
vector<int> preorderTraversal_1(TreeNode *root) {
vector<int> res;
stack<TreeNode *> stk;
TreeNode *cur = root;
while (cur || !stk.empty())
{
if (cur)
{
res.push_back(cur->val);
stk.push(cur);
cur = cur->left;
}
else if (!stk.empty())
{
cur = stk.top()->right;
stk.pop();
}
}
return res;
}
vector<int> preorderTraversal_2(TreeNode *root) {
vector<int> res;
preorderTraversalRe(root, res);
return res;
}
void preorderTraversalRe(TreeNode *node, vector<int> &res) {
if (!node) return;
res.push_back(node->val);
preorderTraversalRe(node->left, res);
preorderTraversalRe(node->right, res);
}
vector<int> preorderTraversal_3(TreeNode *root) {
vector<int> res;
TreeNode *cur = root;
while (cur)
{
if (cur->left)
{
TreeNode *prev = cur->left;
while (prev->right && prev->right != cur)
prev = prev->right;
if (prev->right == cur)
{
cur = cur->right;
prev->right = NULL;
}
else
{
res.push_back(cur->val);
prev->right = cur;
cur = cur->left;
}
}
else
{
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
}; -
- 時間: 2014-9-23 13:23Problem Name: Binary Tree Zigzag Level Order Traversal
Description:
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]
] -
- 時間: 2014-9-23 13:24Now comes the solution (in C++) ...
1. Queue + reverse.
2. Two stacks.
3. Vector. Contributed by yinlinglin.
代碼: /**
* 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>> zigzagLevelOrder(TreeNode *root) {
return zigzagLevelOrder_1(root);
}
// solution 1: Queue + Reverse.
vector<vector<int>> zigzagLevelOrder_1(TreeNode *root) {
vector<vector<int>> res;
if (!root) return res;
queue<TreeNode *> q;
q.push(root);
q.push(NULL); // end indicator of one level
bool left2right = true;
vector<int> level;
while (true)
{
TreeNode *node = q.front(); q.pop();
if (node)
{
level.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
else
{
if (!left2right)
reverse(level.begin(), level.end());
res.push_back(level);
level.clear();
if (q.empty()) break;
q.push(NULL);
left2right = !left2right;
}
}
return res;
}
// Solution 2: Two stacks.
vector<vector<int>> zigzagLevelOrder_2(TreeNode *root) {
vector<vector<int>> res;
if (!root) return res;
stack<TreeNode *> stk[2];
bool left2right = true;
int cur = 1, last = 0;
stk[last].push(root);
vector<int> level;
while (!stk[last].empty())
{
TreeNode *node = stk[last].top();
stk[last].pop();
if (node)
{
level.push_back(node->val);
if (left2right)
{
stk[cur].push(node->left);
stk[cur].push(node->right);
}
else
{
stk[cur].push(node->right);
stk[cur].push(node->left);
}
}
if (stk[last].empty())
{
if (!level.empty())
res.push_back(level);
level.clear();
swap(cur, last);
left2right = !left2right;
}
}
return res;
}
// Solution 3: Vector. Contributed by yinlinglin.
// Compared to solution 1&2, this solution costs a little more space.
// This solution uses only one single vector instead of two stacks in solution 2.
vector<vector<int>> zigzagLevelOrder_3(TreeNode *root) {
vector<vector<int>> result;
if(!root) return result;
vector<TreeNode*> v;
v.push_back(root);
bool left2right = true;
int begin = 0, end = 0;
while(begin <= end)
{
vector<int> row;
for (int i = end; i >= begin; --i)
{
if (!v[i]) continue;
row.push_back(v[i]->val);
if(left2right)
{
v.push_back(v[i]->left);
v.push_back(v[i]->right);
}
else
{
v.push_back(v[i]->right);
v.push_back(v[i]->left);
}
}
if (!row.empty())
result.push_back(row);
begin = end + 1;
end = v.size() - 1;
left2right = !left2right;
}
return result;
}
};
-
- 時間: 2014-9-23 13:27Problem Name: Candy
Description:
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give? -
- 時間: 2014-9-23 13:28Now comes the solution (in C++) ...
You may refer to github.com/AnnieKim/IT...%9E%9C.cpp
1. traverse only once with O(1) space. 2. O(n) space.
代碼: class Solution {
public:
int candy(vector<int> &ratings) {
return candy_1(ratings);
}
int candy_1(vector<int> &ratings) {
int N = ratings.size();
if (N == 0) return 0;
int candy = 1, res = 1;
int maxValue = 1, maxIndex = 0;
for (int i = 1; i < N; ++i)
{
if (ratings[i] >= ratings[i-1])
{
candy = ratings[i] == ratings[i-1] ? 1 : candy + 1;
maxValue = candy;
maxIndex = i;
}
else
{
if (candy == 1) {
if (maxValue <= i - maxIndex) {
res += i - maxIndex;
maxValue++;
} else {
res += i - maxIndex - 1;
}
}
candy = 1;
}
res += candy;
}
return res;
}
int candy_2(vector<int> &ratings) {
int N = ratings.size();
if (N == 0) return 0;
int candy[N];
for (int i = 0; i < N; ++i)
candy[i] = 1;
for (int i = 1; i < N; ++i)
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
for (int i = N-2; i >= 0; --i)
if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])
candy[i] = candy[i+1] + 1;
int res = 0;
for (int i = 0; i < N; ++i)
res += candy[i];
return res;
}
}; -
- 時間: 2014-9-23 13:32
Leetcode Hacking Practice -- Solution in C++ Part 1
