# 117. Populating Next Right Pointers in Each Node II

Difficulty: Hard

Frequency: N/A

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

```         1
/  \
2    3
/ \    \
4   5    7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \    \
4-> 5 -> 7 -> NULL```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
if (!root) return;
root->next = NULL;
while (cur) {
while (nn) {
if (ln) {
if (rn) ln->next = rn;
else {
while (tmp) {
if (!tmp->next) {
ln->next = NULL;
break;
} else if (tmp->next->left) {
ln->next = tmp->next->left;
break;
} else if (tmp->next->right) {
ln->next = tmp->next->right;
break;
}
tmp = tmp->next;
}
}
}
if (rn) {
while (tmp) {
if (!tmp->next) {
rn->next = NULL;
break;
} else if (tmp->next->left) {
rn->next = tmp->next->left;
break;
} else if (tmp->next->right) {
rn->next = tmp->next->right;
break;
}
tmp = tmp->next;
}
}
nn = nn->next;
}
while (cur) {
if (cur->left) {
cur = cur->left;
break;
} else if (cur->right) {
cur = cur->right;
break;
}
cur = cur->next;
}
}
}
};
```

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

Things to learn:

# 098. Validate Binary Search Tree

Difficulty: Medium

Frequency: N/A

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.

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:
bool isValidBST(TreeNode* root) {
return checkBST(root, NULL, NULL);
}
bool checkBST(TreeNode* node, TreeNode* min, TreeNode* max) {
if (!node) return true;
if (min && node->val <= min->val || max && node->val >= max->val) return false;
return checkBST(node->left, min, node) && checkBST(node->right, node, max);
}
};
```

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

Things to learn:

# 116. Populating Next Right Pointers in Each Node

Difficulty: Medium

Frequency: N/A

Given a binary tree

```    struct TreeLinkNode {
}
```

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`.

Initially, all next pointers are set to `NULL`.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

```         1
/  \
2    3
/ \  / \
4  5  6  7
```

After calling your function, the tree should look like:

```         1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL```

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
if (!root) return;
root->next = NULL;
while (cur) {
while (nn) {
if (ln) ln->next = rn;
if (rn) {
if (nn->next) rn->next = nn->next->left;
else rn->next = NULL;
}
nn = nn->next;
}
cur = cur->left;
}
}
};
```

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

Things to learn:

# 106. Construct Binary Tree from Inorder and Postorder Traversal

Difficulty: Medium

Frequency: N/A

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty() || inorder.size() != postorder.size()) return NULL;
return generateTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* generateTree(vector<int>& inorder, int is, int ie, vector<int>& postorder, int ps, int pe) {
if (ps > pe) return NULL;
TreeNode *node = new TreeNode(postorder[pe]);
int mid = is;
while (mid <= ie) {
if (inorder[mid] == postorder[pe]) break;
mid++;
}
node->left = generateTree(inorder, is, mid - 1, postorder, ps, ps + mid - is - 1);
node->right = generateTree(inorder, mid + 1, ie, postorder, pe + mid - ie, pe - 1);
return node;
}
};
```

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

Things to learn:

# 105. Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium

Frequency: N/A

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) return NULL;
return generateTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}
TreeNode* generateTree(vector<int>& preorder, int ps, int pe, vector<int>& inorder, int is, int ie) {
if (ps > pe) return NULL;
TreeNode *node = new TreeNode(preorder[ps]);
int mid = is;
while (mid <= ie) {
if (inorder[mid] == preorder[ps]) break;
mid++;
}
node->left = generateTree(preorder, ps + 1, ps + mid - is, inorder, is, mid - 1);
node->right = generateTree(preorder, pe - ie + mid + 1, pe, inorder, mid + 1, ie);
return node;
}
};
```

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

Things to learn:

# 109. Convert Sorted List to Binary Search Tree

Difficulty: Medium

Frequency: N/A

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* 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:
while(fast && fast->next) {
fast = fast->next->next;
pre = slow;
slow = slow->next;
}
if (pre) pre->next = NULL;
TreeNode *root = new TreeNode(slow->val);
root->right = sortedListToBST(slow->next);
return root;
}
};
```

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

Things to learn:

# 114. Flatten Binary Tree to Linked List

Difficulty: Medium

Frequency: N/A

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
```

click to show hints.

Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

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:
void flatten(TreeNode* root) {
TreeNode *cur = root;
while(cur) {
if (cur->left) {
TreeNode *tmp = cur->left;
while(tmp->right) {
tmp = tmp->right;
}
tmp->right = cur->right;
cur->right = cur->left;
cur->left = NULL;
}
cur = cur->right;
}
}
};
```

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

Things to learn:

# 129. Sum Root to Leaf Numbers

Difficulty: Medium

Frequency: N/A

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

For example,

```    1
/ \
2   3
```

The root-to-leaf path `1->2` represents the number `12`.
The root-to-leaf path `1->3` represents the number `13`.

Return the sum = 12 + 13 = `25`.

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 sumNumbers(TreeNode* root) {
int sum = 0;
getSum(root, 0, sum);
return sum;
}
void getSum(TreeNode* node, int curSum, int& sum) {
if (!node) return;
curSum = curSum * 10 + node->val;
if (!node->left && !node->right) {
sum += curSum;
return;
}
getSum(node->left, curSum, sum);
getSum(node->right, curSum, sum);
}
};
```

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

Things to learn:

# 113. Path Sum II

Difficulty: Medium

Frequency: N/A

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and `sum = 22`,

```              5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1
```

return

```[
[5,4,11,2],
[5,8,4,5]
]```

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>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> results;
vector<int> result;
getPaths(root, 0, result, sum, results);
return results;
}
void getPaths(TreeNode* node, int curSum, vector<int> result, int sum, vector<vector<int>>& results) {
if (!node) return;
curSum += node->val;
result.push_back(node->val);
if (!node->left && !node->right && curSum == sum) {
results.push_back(result);
return;
}
getPaths(node->left, curSum, result, sum, results);
getPaths(node->right, curSum, result, sum, results);
}
};
```

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

Things to learn:

# 257. Binary Tree Paths

Difficulty: Easy

Frequency: N/A

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

```   1
/   \
2     3
\
5
```

All root-to-leaf paths are:

`["1->2->5", "1->3"]`

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<string> binaryTreePaths(TreeNode* root) {
vector<string> results;
getPaths(root, "", results);
return results;
}
void getPaths(TreeNode *node, string result, vector<string>& results) {
if (!node) return;
result += to_string(node->val);
result += "->";
if (!node->left && !node->right) {
results.push_back(result.substr(0, result.size() - 2));
return;
}
getPaths(node->left, result, results);
getPaths(node->right, result, results);
}
};
```

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

Things to learn: