# 107. Binary Tree Level Order Traversal II

Difficulty: Easy

Frequency: N/A

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

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

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

```[
[15,7],
[9,20],

]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* 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>> results;
if (!root) return results;
queue<TreeNode*> myQ;
myQ.push(root);
while (!myQ.empty()) {
int q_size = myQ.size();
vector<int> tmp;
while (q_size) {
TreeNode *cur = myQ.front();
tmp.push_back(cur->val);
myQ.pop();
if (cur->left) myQ.push(cur->left);
if (cur->right) myQ.push(cur->right);
q_size--;
}
results.push_back(tmp);
}
return vector<vector<int>> (results.rbegin(), results.rend());
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 102. Binary Tree Level Order Traversal

Difficulty: Easy

Frequency: N/A

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:

```[
,
[9,20],
[15,7]
]```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> results;
if (!root) return results;
queue<TreeNode*> myQ;
myQ.push(root);
while (!myQ.empty()) {
vector<int> tmp;
int q_size = myQ.size();
while (q_size) {
TreeNode *cur = myQ.front();
tmp.push_back(cur->val);
myQ.pop();
if (cur->left) myQ.push(cur->left);
if (cur->right) myQ.push(cur->right);
q_size--;
}
results.push_back(tmp);
}
return results;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 124. Binary Tree Maximum Path Sum

Difficulty: Hard

Frequency: N/A

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

```       1
/ \
2   3
```

Return `6`.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* 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 maxVal = INT_MIN;
getMaxSum(root, maxVal);
return maxVal;
}
int getMaxSum(TreeNode* node, int& maxVal) {
if (!node) return 0;
int l = getMaxSum(node->left, maxVal);
int r = getMaxSum(node->right, maxVal);
if (l < 0) l = 0;
if (r < 0) r = 0;
if (l + r + node->val > maxVal) maxVal = l + r + node->val;
return node->val += max(l, r);
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

# 099. Recover Binary Search Tree

Difficulty: Hard

Frequency: N/A

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?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
TreeNode *first = NULL, *second = NULL, *pre = new TreeNode(INT_MIN);
public:
void recoverTree(TreeNode* root) {
tranverseTree(root);
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
void tranverseTree(TreeNode* node) {
if (!node) return;
tranverseTree(node->left);
if (!first && node->val < pre->val) first = pre;
if (first && node->val < pre->val) second = node;
pre = node;
tranverseTree(node->right);
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: