- Binary tree traversal: preorder -> 中左右；inorder->左中右；postorder->左右中
// 144. Binary Tree Preorder Traversal
// Method 1: traverse
vector<int> ans;
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return {};
ans.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return ans;
}
// Method 2: non-recursive
vector<int> preorderTraversal(TreeNode* root) {
if (!root) return {};
vector<int> ans;
stack<TreeNode*> record;
record.push(root);
while (!record.empty()) {
const auto tp = record.top();
ans.push_back(tp->val);
record.pop();
if (tp->right != nullptr) record.push(tp->right);
if (tp->left != nullptr) record.push(tp->left);
}
return ans;
}
// 94. Binary Tree Inorder Traversal
// Method 1
vector<int> ans;
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
inorderTraversal(root->left);
ans.push_back(root->val);
inorderTraversal(root->right);
return ans;
}
// Method 2
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
stack<TreeNode*> record;
vector<int> ans;
while (root != nullptr || !record.empty()) {
while (root !=nullptr) {
record.push(root);
root = root->left;
}
root = record.top();
ans.push_back(root->val);
record.pop();
root = root->right;
}
return ans;
}
// 145. Binary Tree Postorder Traversal
// Method 1
vector<int> ans;
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
postorderTraversal(root->left);
postorderTraversal(root->right);
ans.push_back(root->val);
return ans;
}
// Method 2
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
stack<TreeNode*> record;
record.push(root);
vector<int> ans;
while (root != nullptr && !record.empty()) {
const auto tp = record.top();
ans.push_back(tp->val);
record.pop();
if (tp->left) record.push(tp->left);
if (tp->right) record.push(tp->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
// 589. N-ary Tree Preorder Traversal
void PreorderTraversal(Node* root, vector<int>& nums) {
if (root == nullptr) return;
nums.push_back(root->val);
for (const auto ptr : root->children) {
PreorderTraversal(ptr, nums);
}
}
vector<int> preorder(Node* root) {
vector<int> pre_nums;
PreorderTraversal(root, pre_nums);
return pre_nums;
}
// 590. N-ary Tree Postorder Traversal
void PostOrderTraversal(Node* root, vector<int>& nums) {
if (root == nullptr) return;
for (const auto ptr : root->children)
PostOrderTraversal(ptr, nums);
nums.push_back(root->val);
}
vector<int> postorder(Node* root) {
vector<int> nums;
PostOrderTraversal(root, nums);
return nums;
}
// 429. N-ary Tree Level Order Traversal
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
queue<Node*> cur_level;
if (root != nullptr) cur_level.push(root);
while (!cur_level.empty()) {
vector<int> cur_nums;
int size = cur_level.size();
for (int idx = 0; idx < size; ++idx) {
const auto ptr = cur_level.front();
cur_level.pop();
cur_nums.push_back(ptr->val);
for (const auto ptr2 : ptr->children)
if (ptr2 != nullptr) cur_level.push(ptr2);
}
ans.push_back(cur_nums);
}
return ans;
}
// 776. Split BST
vector<TreeNode*> splitBST(TreeNode* root, int target) {
vector<TreeNode*> ans(2, nullptr);
if (!root) return ans;
if (root->val > target) {
ans[1] = root;
const auto res = splitBST(root->left, target);
root->left = res[1];
ans[0] = res[0];
} else {
ans[0] = root;
const auto res = splitBST(root->right, target);
root->right = res[0];
ans[1] = res[1];
}
return ans;
}
- Level Order Traversal
// 102. Binary Tree Level Order Traversal
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode*> record;
record.push(root);
while (!record.empty()) {
int len = record.size();
vector<int> level;
for (int idx = 0; idx < len; ++idx) {
const auto tp = record.front();
level.push_back(tp->val);
record.pop();
if (tp->left != nullptr) record.push(tp->left);
if (tp->right != nullptr) record.push(tp->right);
}
ans.push_back(level);
}
return ans;
}
// Method 2
void LevelOrderBottom(TreeNode* root, int level) {
if (!root) return;
if (ans.size() <= level) ans.push_back({});
ans[level].push_back(root->val);
LevelOrderBottom(root->left, level + 1);
LevelOrderBottom(root->right, level + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
LevelOrderBottom(root, 0);
return ans;
}
// 107. Binary Tree Level Order Traversal II
// Method 1 BFS
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if (root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode*> record;
record.push(root);
while (!record.empty()) {
int len = record.size();
vector<int> level;
for (int idx = 0; idx < len; ++idx) {
const auto tp = record.front();
level.push_back(tp->val);
record.pop();
if (tp->left != nullptr) record.push(tp->left);
if (tp->right != nullptr) record.push(tp->right);
}
ans.push_back(level);
}
reverse(ans.begin(), ans.end());
return ans;
}
// Method 2 DFS
vector<vector<int>> ans;
void LevelOrderBottom(TreeNode* root, int level) {
if (!root) return;
if (ans.size() <= level) ans.push_back({});
ans[level].push_back(root->val);
LevelOrderBottom(root->left, level + 1);
LevelOrderBottom(root->right, level + 1);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
LevelOrderBottom(root, 0);
reverse(ans.begin(), ans.end());
return ans;
}
// 103. Binary Tree Zigzag Level Order Traversal
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> cur_level;
cur_level.push(root);
bool is_odd = true;
while (!cur_level.empty()) {
int size = cur_level.size();
int idx = 0;
vector<int> cur_value;
while (idx < size) {
const auto tp = cur_level.front();
cur_value.push_back(tp->val);
cur_level.pop();
if (tp->left) cur_level.push(tp->left);
if (tp->right) cur_level.push(tp->right);
++idx;
}
if (!is_odd) {
reverse(cur_value.begin(), cur_value.end());
}
ans.push_back(cur_value);
is_odd ^= 1;
}
return ans;
}
// 255. Verify Preorder Sequence in Binary Search Tree
bool VerifyPreorder(vector<int>& nums, int stt_idx,
int fin_idx, int val, bool is_right) {
if (fin_idx <= stt_idx) return true;
if (is_right) {
for (int idx = stt_idx; idx <= fin_idx; ++idx) {
if (nums[idx] < val) return false;
}
}
int new_val = nums[stt_idx];
int cut_idx = stt_idx;
for (int idx = stt_idx; idx <= fin_idx; ++idx) {
if (nums[idx] > new_val) {
cut_idx = idx - 1;
break;
} else cut_idx = idx;
}
return VerifyPreorder(nums, stt_idx + 1, cut_idx,
new_val, false) &&
VerifyPreorder(nums, cut_idx + 1, fin_idx,
new_val, true);
}
bool verifyPreorder(vector<int>& preorder) {
return VerifyPreorder(preorder, 0, preorder.size() - 1,
INT_MIN, true);
}
// 366. Find Leaves of Binary Tree
int FindLeaves(TreeNode* root, vector<vector<int>>& record) {
if (!root) return -1;
if (!root->left && !root->right) {
if (!record.size()) record.emplace_back(vector<int>());
record[0].emplace_back(root->val);
return 0;
}
const int index_left = FindLeaves(root->left, record);
const int index_right = FindLeaves(root->right, record);
const int index_root = max(index_left, index_right) + 1;
if (record.size() < index_root + 1)
record.emplace_back(vector<int>());
record[index_root].emplace_back(root->val);
return index_root;
}
vector<vector<int>> findLeaves(TreeNode* root) {
vector<vector<int>> ans;
FindLeaves(root, ans);
return ans;
}
// 428. Serialize and Deserialize N-ary Tree
class Codec {
public:
// Encodes a tree to a single string.
string serialize(Node* root) {
if (!root) return "";
string ans = "(" + to_string(root->val);
for (const auto ptr : root->children) {
ans += serialize(ptr);
}
ans += ")";
return ans;
}
// Decodes your encoded data to tree.
std::string::size_type sz;
Node* deserialize(string data) {
if (data.empty()) return nullptr;
string data2 = data.substr(1, data.size()-2);
if (data2.empty()) return nullptr;
string cur;
int count = 0;
int i = 0;
while (data2[i] >= '0' && data2[i] <= '9') {
cur += data2[i];
++i;
}
Node* head = new Node(stoi(cur, &sz));
cur.clear();
while (i < data2.size()) {
if (data2[i] == '(') {
++count;
cur += data2[i];
} else if (data2[i] == ')') {
--count;
cur += data2[i];
if (!count) {
head->children.emplace_back(deserialize(cur));
cur.clear();
}
} else cur += data2[i];
++i;
}
if (!cur.empty()) head->children.emplace_back(deserialize(cur));
return head;
}
};
- Construct binary tree from different orders
// 105. Construct Binary Tree from Preorder and Inorder Traversal
TreeNode* BuildTree(vector<int>& preorder, int pre_stt_idx, int pre_fin_idx,
vector<int>& inorder, int in_stt_idx, int in_fin_idx) {
if (pre_stt_idx > pre_fin_idx) return nullptr;
if (pre_stt_idx == pre_fin_idx) return new TreeNode(preorder[pre_stt_idx]);
int root_val = preorder[pre_stt_idx];
int left_idx = in_stt_idx;
while (inorder[left_idx] != root_val) ++left_idx;
int num_left = left_idx - in_stt_idx;
TreeNode* left_node = BuildTree(preorder, pre_stt_idx + 1,
pre_stt_idx + num_left,
inorder, in_stt_idx, left_idx - 1);
TreeNode* right_node = BuildTree(preorder, pre_stt_idx + num_left + 1,
pre_fin_idx, inorder,
left_idx + 1, in_fin_idx);
return new TreeNode(root_val, left_node, right_node);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return BuildTree(preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
// 889. Construct Binary Tree from Preorder and Postorder Traversal
TreeNode* BuildTree(vector<int>& inorder, int in_stt_idx, int in_fin_idx,
vector<int>& postorder, int post_stt_idx,
int post_fin_idx) {
if (in_stt_idx > in_fin_idx) return nullptr;
if (in_stt_idx == in_fin_idx) return new TreeNode(inorder[in_stt_idx]);
unordered_map<int, int> record;
int root_val = inorder[in_stt_idx];
int num = 0;
while (num < in_fin_idx - in_stt_idx) {
int in_val = inorder[in_stt_idx + 1 + num];
int post_val = postorder[post_stt_idx + num];
++record[in_val];
--record[post_val];
++num;
if (!record[in_val]) record.erase(in_val);
if (!record[post_val]) record.erase(post_val);
if (record.empty()) break;
}
TreeNode* left_node = BuildTree(inorder, in_stt_idx + 1,
in_stt_idx + num, postorder,
post_stt_idx, post_stt_idx + num - 1);
TreeNode* right_node = BuildTree(inorder, in_stt_idx + num + 1,
in_fin_idx, postorder,
post_stt_idx + num, post_fin_idx - 1);
return new TreeNode(root_val, left_node, right_node);
}
TreeNode* constructFromPrePost(vector<int>& inorder, vector<int>& postorder) {
return BuildTree(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}
// 106. Construct Binary Tree from Inorder and Postorder Traversal
TreeNode* BuildTree(vector<int>& inorder, int in_stt_idx, int in_fin_idx,
vector<int>& postorder, int post_stt_idx,
int post_fin_idx) {
if (in_stt_idx > in_fin_idx) return nullptr;
if (in_stt_idx == in_fin_idx) return new TreeNode(inorder[in_stt_idx]);
int root_val = postorder[post_fin_idx];
int left_idx = in_stt_idx;
while (inorder[left_idx] != root_val) ++left_idx;
int left_num = left_idx - in_stt_idx;
TreeNode* left_node = BuildTree(inorder, in_stt_idx,
in_stt_idx + left_num - 1, postorder,
post_stt_idx, post_stt_idx + left_num - 1);
TreeNode* right_node = BuildTree(inorder, in_stt_idx + left_num + 1,
in_fin_idx, postorder,
post_stt_idx + left_num, post_fin_idx - 1);
return new TreeNode(root_val, left_node, right_node);
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return BuildTree(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}
// 1008. Construct Binary Search Tree from Preorder Traversal
TreeNode* BstFromPreorder(vector<int>& preorder,
int stt_idx, int fin_idx) {
if (stt_idx > fin_idx) return nullptr;
if (stt_idx == fin_idx) return new TreeNode(preorder[stt_idx]);
int root_val = preorder[stt_idx];
int left_idx = stt_idx + 1;
while (left_idx < preorder.size() &&
preorder[left_idx] < root_val) ++left_idx;
TreeNode* left = BstFromPreorder(preorder, stt_idx + 1, left_idx - 1);
TreeNode* right = BstFromPreorder(preorder, left_idx, fin_idx);
return new TreeNode(root_val, left, right);
}
TreeNode* bstFromPreorder(vector<int>& preorder) {
return BstFromPreorder(preorder, 0, preorder.size() - 1);
}
// 971. Flip Binary Tree To Match Preorder Traversal
// Find right border with fin_idx; change child if needed.
vector<int> flip_vec;
bool FlipMatchVoyage(TreeNode* root, vector<int>& voyage,
int stt_idx, int fin_idx) {
if (root == nullptr && stt_idx > fin_idx) return true;
if (voyage[stt_idx] != root->val) return false;
if (stt_idx == fin_idx && (!root->left && !root->right))
return true;
int left_root_val = root->left == nullptr?-1:root->left->val;
int right_root_val = root->right == nullptr?-1:root->right->val;
if (left_root_val != voyage[stt_idx + 1] &&
right_root_val != voyage[stt_idx + 1]) return false;
if (root->left != nullptr && left_root_val != voyage[stt_idx+1]) {
swap(root->left, root->right);
flip_vec.push_back(root->val);
}
right_root_val = root->right == nullptr?-1:root->right->val;
int left_idx = stt_idx + 1;
while (left_idx <= fin_idx && voyage[left_idx] != right_root_val)
++left_idx;
bool left_res = FlipMatchVoyage(root->left, voyage,
stt_idx + 1, left_idx - 1);
if (!left_res) return false;
bool right_res = FlipMatchVoyage(root->right, voyage,
left_idx, fin_idx);
return right_res;
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
bool flip_res = FlipMatchVoyage(root, voyage, 0, voyage.size() - 1);
if (!flip_res) return {-1};
return flip_vec;
}
// Left & right merge
// 96. Unique Binary Search Trees
int record[20][20];
int GetUniqueSearch(const int stt, const int fin) {
if (stt > fin) return 1;
if (record[stt][fin] > 0)
return record[stt][fin];
int ttl_num = 0;
for (int index = stt; index <= fin; ++index) {
ttl_num += GetUniqueSearch(stt, index-1) * GetUniqueSearch(index+1, fin);
}
record[stt][fin] = ttl_num;
return record[stt][fin];
}
int numTrees(int n) {
memset(record, 0, sizeof(record));
return GetUniqueSearch(1, n);
}
// 95. Unique Binary Search Trees II
vector<TreeNode*> GetUniqueTree(const int stt, const int fin) {
if (stt > fin) return {nullptr};
if (stt == fin) {
return {new TreeNode(stt)};
}
vector<TreeNode*> ans;
for (int index = stt; index <= fin; ++index) {
vector<TreeNode*> left = GetUniqueTree(stt, index-1);
vector<TreeNode*> right = GetUniqueTree(index+1, fin);
for (const auto l : left) {
for (const auto r : right) {
TreeNode* root = new TreeNode(index);
root->left = l;
root->right = r;
ans.emplace_back(root);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
if (n <= 0) {
return {};
}
return GetUniqueTree(1, n);
}
// 99. Recover Binary Search Tree
// Method 1: iterative with inorder
void recoverTree(TreeNode* root) {
stack<TreeNode*> record;
TreeNode* last_node = nullptr;
TreeNode* x = nullptr;
TreeNode* y = nullptr;
while (root || !record.empty()) {
while (root) {
record.emplace(root);
root = root->left;
}
TreeNode* cur_node = record.top();
record.pop();
if (cur_node->right)
root = cur_node->right;
if (last_node && cur_node->val < last_node->val) {
y = cur_node;
if (!x) x = last_node;
else break;
}
last_node = cur_node;
}
const int val = y->val;
y->val = x->val;
x->val = val;
}
// Method 2: recursion
TreeNode* x = nullptr;
TreeNode* y = nullptr;
TreeNode* last = nullptr;
void Swap(TreeNode* x, TreeNode* y) {
if (!x || !y) return;
const int val = x->val;
x->val = y->val;
y->val = val;
}
void recoverTree(TreeNode* root) {
RecoverTree(root);
Swap(x, y);
}
void RecoverTree(TreeNode* root) {
if (!root) return;
RecoverTree(root->left);
if (last && last->val > root->val) {
y = root;
if (!x) {
x = last;
} else return;
}
last = root;
RecoverTree(root->right);
}
- BST Succesor
// 285. Inorder Successor in BST
// Method 1
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
if (root == nullptr || p == nullptr) return nullptr;
TreeNode* ans = nullptr;
const int p_val = p->val;
while (root != nullptr) {
if (root->val > p_val) {
ans = root;
root = root->left;
} else {
root = root->right;
}
}
return ans;
}
// Method 2
void inorderSuccessorNode(TreeNode* const root, TreeNode* const p, TreeNode* &ans) {
if(!root) return;
if (root->val > p->val) {
if (ans == nullptr || root->val < ans->val) {
ans = root;
}
inorderSuccessorNode(root->left, p, ans);
} else {
inorderSuccessorNode(root->right, p, ans);
}
}
// 510. Inorder Successor in BST II
Node* inorderSuccessor(Node* node) {
if (node == nullptr) return nullptr;
Node* cur_node = node;
Node* cur_right = node->right;
if (cur_right != nullptr) {
while (cur_right->left != nullptr) {
cur_right = cur_right->left;
}
}
if (cur_right != nullptr) return cur_right;
while (cur_node->parent != nullptr) {
if (cur_node->parent->left == cur_node) {
return cur_node->parent;
}
cur_node = cur_node->parent;
}
return nullptr;
}
// 987. Vertical Order Traversal of a Binary Tree
//positioning based and replicate position
void VerticalTraversal(TreeNode* root, int row, int col,
map<int, map<int, multiset<int>>>& record) {
if (!root) return;
record[col][row].insert(root->val);
VerticalTraversal(root->left, row + 1, col - 1, record);
VerticalTraversal(root->right, row + 1, col + 1, record);
}
vector<vector<int>> verticalTraversal(TreeNode* root) {
map<int, map<int, multiset<int>>> record;
VerticalTraversal(root, 0, 0, record);
vector<vector<int>> ans;
for (const auto line : record) {
const auto line_data = line.second;
vector<int> line_vec;
for (const auto ele : line_data) {
const auto nums = ele.second;
for (const auto num : nums) {
line_vec.push_back(num);
}
}
ans.push_back(line_vec);
}
return ans;
}
// 116. Populating Next Right Pointers in Each Node
Node* connect(Node* root) {
if (!root) return nullptr;
if (root->left) {
root->left->next = root->right;
}
if (root->right && root->next) {
root->right->next = root->next->left;
}
connect(root->right);
connect(root->left);
return root;
}
// 117. Populating Next Right Pointers in Each Node II
Node* connect(Node* root) {
if (!root) return nullptr;
if (root->left && root->right) {
root->left->next = root->right;
}
if ((root->left && !root->right) || (root->right && !root->left) || (root->left && root->right)) {
auto node = root->next;
Node* cur_node = !root->right ? root->left : root->right;
while (node) {
if (node->left || node->right) {
cur_node->next = node->left ? node->left : node->right;
break;
}
node = node->next;
}
}
connect(root->right);
connect(root->left);
return root;
}
// 272. Closest Binary Search Tree Value II
// O(n) solution
deque<int> data_;
vector<int> closestKValues(TreeNode* root, double target, int k) {
Inorder(root);
while (data_.size() > k) {
const double diff_prev = abs(data_.front() - target);
const double diff_suc = abs(data_.back() - target);
if (diff_prev > diff_suc) {
data_.pop_front();
} else {
data_.pop_back();
}
}
return vector<int>(begin(data_), end(data_));
}
void Inorder(const TreeNode* root) {
if (!root) return;
Inorder(root->left);
data_.emplace_back(root->val);
Inorder(root->right);
}
// Another solution is the iterative solution with successor and pre.
// 450. Delete Node in a BST
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return nullptr;
TreeNode* parent = nullptr;
TreeNode* cur = root;
while (cur != nullptr) {
if (cur->val > key) {
parent = cur;
cur = cur->left;
} else if (cur->val < key) {
parent = cur;
cur = cur->right;
} else {
break;
}
}
if (!cur) return root;
TreeNode* mark = cur;
if (cur->left) {
parent = cur;
cur = cur->left;
while (cur->right) {
parent = cur;
cur = cur->right;
}
mark->val = cur->val;
if (parent->left == cur)
parent->left = cur->left;
else parent->right = cur->left;
} else if (cur->right) {
parent = cur;
cur = cur->right;
while (cur->left) {
parent = cur;
cur = cur->left;
}
mark->val = cur->val;
if (parent->right == cur)
parent->right = cur->right;
else
parent->left = cur->right;
} else {
if (!parent) return nullptr;
if (parent->left == cur) parent->left = nullptr;
if (parent->right == cur) parent->right = nullptr;
}
return root;
}