Intro
Concepts
Full Binary Tree: 全部都填满的树。
Complete Binary Tree: 除了最后一行其他都填满，最后一行的最后一个之前（左边）全部是满的。
Balanced Binary Tree: 左右子树的高度最多差1. Height of the tree: $O(log(n))$
Binary Search Tree: Recursively, Leftsubtree is smaller than root and righ subtree is larger than root. Inorder traverse is increasing.
Traverse
Example
- Preorder: 8->3->1->6->4->7->10->14->13
- Inorder: 1->3->4->6->7->8->10->13->14
- Postorder: 1->4->7->6->3->13->14->10->8
- Levelorder: 8->3->10->1->6->14->4->7->13
Traverse Recursively
void helper(TreeNode* node, vector<int> & rst){
if (node != nullptr){
// rst.emplace_back(root -> val); If it is PreOder
helper(node -> left, rst);
// rst.emplace_back(root -> val); If it is InOrder
helper(node -> right, rst);
// rst.emplace_back(root -> val); If it is PostOrder
}
}
vector<int> DFS_Traversal(TreeNode* root) {
// write your code here
vector<int> rst;
helper(root, rst);
return rst;
}
Preorder iterative
void pushleft(TreeNode* root, stack<TreeNode*> & s, vector<int> & res) {
while (root) {
res.emplace_back(root->val);
s.push(root);
root = root->left;
}
}
vector<int> preorder(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
pushleft(root, s, res);
while (!s.empty()) {
auto cur = s.top();
s.pop();
cur = cur->right;
pushleft(cur, s, res);
}
return res;
}
Inorder Iterative
void pushleft(TreeNode* root, stack<TreeNode*> & s) {
while (root) {
s.push(root);
root = root->left;
}
}
vector<int> inorder(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
pushleft(root, s);
while (!s.empty()) {
auto cur = s.top();
s.pop();
res.emplace_back(cur->val);
cur = cur->right;
pushleft(cur, s);
}
return res;
}
Postorder iterative I
vector<int> postorder(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
auto cur = s1.top();
s2.push(cur);
s1.pop();
if (cur->left) {
s1.push(cur->left);
}
if (cur->right) {
s1.push(cur->right);
}
}
while (!s2.empty()) {
auto cur = s2.top();
s2.pop();
res.emplace_back(cur->val);
}
return res;
}
Postorder iterative II
vector<int> postorderII(TreeNode* root) {
if (root == nullptr) {
return {};
}
vector<int> res;
stack<TreeNode*> s;
s.push(root);
TreeNode* prev = nullptr;
while (!s.empty()) {
auto cur = s.top();
if (prev == nullptr || cur == prev->left || cur == prev->right) {
if (cur->left) {
s.push(cur->left);
}
else if (cur->right) {
s.push(cur->right);
}
else {
s.pop();
res.emplace_back(cur->val);
}
}
else if (prev == cur->right || prev == cur->left && cur->right == nullptr) {
s.pop();
res.emplace_back(cur->val);
}
else {
s.push(cur->right);
}
prev = cur;
}
return res;
}
BFS level order
vector<vector<int>> levelOrder(TreeNode *root) {
vector<vector<int>> rst;
if (root == nullptr) return rst;
queue<TreeNode*> nodes;
nodes.push(root);
while(!nodes.empty()){
vector<int> level;
int size = nodes.size();
for (int i = 0; i < size; i++){
TreeNode* node = nodes.front();
nodes.pop();
level.emplace_back(node -> val);
if (node -> left != nullptr) nodes.push(node -> left);
if (node -> right != nullptr) nodes.push(node -> right);
}
rst.emplace_back(level);
}
return rst;
}
Morris Traverse(TODO)
Binary Tree Iterator
Implementation
BST iterator
class BSTIterator {
private:
stack<TreeNode*> s;
public:
BSTIterator(TreeNode *root) {
while (root) {
s.push(root);
root = root -> left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
//which means ascending order
//which means inoredr traversal
int next() {
if (s.empty()) {
return INT_MAX;
}
TreeNode* parent = s.top();
s.pop();
TreeNode* cur = parent -> right;
while (cur) {
s.push(cur);
cur = cur -> left;
}
return parent -> val;
}
};
Different views of tree
Boundary of Binary Tree
/**
* 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<int> boundaryOfBinaryTree(TreeNode* root) {
if (root == nullptr) {
return {};
}
vector<int> left, right, bottom, res;
res.emplace_back(root->val);
getLeft(root->left, left);
getBottom(root->left, bottom);
getBottom(root->right, bottom);
getRight(root->right, right);
res.insert(res.end(), left.begin(), left.end());
res.insert(res.end(), bottom.begin(), bottom.end());
res.insert(res.end(), right.rbegin(), right.rend());
return res;
}
private:
void getLeft(TreeNode* root, vector<int> & res) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
return;
}
res.emplace_back(root->val);
if (root->left) {
getLeft(root->left, res);
}
else {
getLeft(root->right, res);
}
}
void getRight(TreeNode* root, vector<int> & res) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
return;
}
res.emplace_back(root->val);
if (root->right) {
getRight(root->right, res);
}
else {
getRight(root->left, res);
}
}
void getBottom(TreeNode* root, vector<int> & res) {
if (root == nullptr) {
return;
}
if (!root->left && !root->right) {
res.emplace_back(root->val);
}
getBottom(root->left, res);
getBottom(root->right, res);
}
};
Path problems
Maximum Path Sum Binary Tree I
Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return INT_MIN (C++).
class Solution {
public:
int global_max = INT_MIN;
int maxPathSum(TreeNode* root){
dfs(root);
return global_max;
}
int dfs(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left = dfs(root -> left);
int right = dfs(root -> right);
if (root -> left && root -> right) {
int sum = left + right + root -> value;
global_max = max(sum, global_max);
return max(left, right) + root -> value;
}
return (!root -> left)? right + root -> value : left + root -> value;
}
};
Maximum Path Sum Binary Tree II
Given a binary tree in which each node contains an integer number. Find the maximum possible sum from any node to any node (the start node and the end node can be the same).
class Solution {
public:
int maxPathSum(TreeNode* root) {
int global_max = INT_MIN;
dfs(root, global_max);
return global_max;
}
int dfs(TreeNode* root, int& global_max) {
if (root == nullptr) {
return 0;
}
int left = dfs(root -> left, global_max);
int right = dfs(root -> right, global_max);
//left = (left < 0)? 0 : left;
//right = (right < 0)? 0 : right;
global_max = max(global_max, left + right + root -> value);
return max(0, max(left, right) + root -> value);
}
};
Maximum Path Sum Binary Tree III
Given a binary tree in which each node contains an integer number. Find the maximum possible subpath sum(both the starting and ending node of the subpath should be on the same path from root to one of the leaf nodes, and the subpath is allowed to contain only one node).
class Solution {
public:
int maxPathSum(TreeNode* root) {
int global_max = INT_MIN;
dfs(root, global_max);
return global_max;
}
int dfs(TreeNode* root, int& global_max) {
if (root == nullptr) {
return 0;
}
int left = dfs(root -> left, global_max);
int right = dfs(root -> right, global_max);
int sum = max(max(left, right) , 0) + root -> value;
global_max = max(global_max, sum);
return sum;
}
};
LCA problems
LCA I
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root -> left, p, q);
TreeNode* right = lowestCommonAncestor(root -> right, p, q);
if (left && right) {
return root;
}
return left? left : right;
}
LCA of BST
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return root;
// p, q are in two sides or root is one of p, q
} else if ((root->val - p->val) * (root->val - q->val) <= 0) {
return root;
//p,q are smaller than root => both in left side
} else if (root->val > p->val && root -> val > q->val) {
return lowestCommonAncestor(root->left, p, q);
//both in right side
} else {
return lowestCommonAncestor(root->right, p, q);
}
}
LCA II
Give the treenode with parent pointer.
//class TreeNodeP {
// public:
// int value;
// TreeNodeP* left;
// TreeNodeP* right;
// TreeNodeP* parent;
// TreeNodeP(int v, TreeNodeP* p)
// : value(v), left(NULL), right(NULL), parent(p) {}
//};
class Solution {
private:
int path_length(TreeNodeP* node) {
int length = 0;
while (node) {
node = node -> parent;
length++;
}
return length;
}
TreeNodeP* llc(TreeNodeP* small, TreeNodeP* large, int diff) {
while (diff > 0) {
large = large -> parent;
diff--;
}
while (large != small) {
large = large -> parent;
small = small -> parent;
}
return large;
}
public:
TreeNodeP* LCA(TreeNodeP* one, TreeNodeP* two) {
int l1 = path_length(one);
int l2 = path_length(two);
if (l1 <= l2) {
return llc(one, two, l2 - l1);
} else {
return llc(two, one, l1 - l2);
}
}
};
LCA III
Given two nodes in a binary tree, find their lowest common ancestor (the given two nodes are not guaranteed to be in the binary tree). Return null If any of the nodes is not in the tree. There is no parent pointer for the nodes in the binary tree. The given two nodes are not guaranteed to be in the binary tree.
class Solution {
public:
bool flag1 = false;
bool flag2 = false;
TreeNode* solve(TreeNode* root, TreeNode* one, TreeNode* two) {
traversal(root, one, two);
if (flag1 && flag2) {
return findLCA(root, one, two);
}
return nullptr;
}
void traversal(TreeNode* root, TreeNode* one, TreeNode* two) {
if (root == nullptr) {
return;
}
if (root == one) {flag1 = true;}
if (root == two) {flag2 = true;}
traversal(root -> left, one, two);
traversal(root -> right, one, two);
}
TreeNode* findLCA(TreeNode* root, TreeNode* one, TreeNode* two) {
if (root == nullptr) {
return nullptr;
}
if (root == one) {
return root;
}
if (root == two) {
return root;
}
auto left = findLCA(root -> left, one, two);
auto right = findLCA(root -> right, one, two);
if (left && right) {
return root;
} else if (left) {
return left;
} else if (right) {
return right;
} else {
return nullptr;
}
}
};
LCA IV
Give k nodes, find their CLA.
class Solution {
public:
TreeNode* LCA(TreeNode* root, vector<TreeNode*> nodes) {
if (root == nullptr) {
return root;
}
for (int i = 0; i < nodes.size(); i++) {
if (root == nodes[i]) {
return root;
}
}
auto left = LCA(root -> left, nodes);
auto right = LCA(root -> right, nodes);
if (left && right) {
return root;
} else {
return left? left : right;
}
}
};
Check if cousins
bool checkIfCousins(TreeNode* root, TreeNode* one, TreeNode* two) {
bool res = false;
helper(root, one, two, 0, res);
return res;
}
//return target'node level
//return -1 is not found
int helper(TreeNode* root, TreeNode* one, TreeNode* Two, int level, bool & res) {
if (root == nullptr) {
return -1;
}
if (root == one || root == two) {
return level;
}
int left = helper(root->left, one, two, level + 1, res);
int right = helper(root->right, one, two, level + 1, res);
if (left == right && left - 1 > level) {
res = true;
}
return max(left, right);
}
Serialize and deserialize binary tree
Reconstruct Binary Tree With Preorder And Inorder
一棵树需要什么信息？需要知道什么是根，左子树和右子树分别又是什么。
那么从这两种遍历之中可以获取什么信息？
先序遍历： root | left subtree | right subtree
中序遍历： left subtree | root | right subtree
先序遍历的最左边，一定是根，但是无法找到左子树和右子树的分界点；但是可以通过找到根，从而从中序遍历中找到这个分界。
解题步骤：
leftmost of preOrder must be root
find position of root in inOrder => need a hashtable to pre-store indices
in inorder: left side of root is left subtree
in inorder: right side of root is right subtree
recursively solve the problem on left subtree and right subtree
TreeNode* reconstruct(vector<int> in, vector<int> pre) {
unordered_map<int, int> table;
for (int i = 0; i < in.size(); i++) {
table[in[i]] = i;
}
return helper(in, 0, in.size() - 1, pre, 0, table);
}
TreeNode* helper(const vector<int> & in, int in_left, int in_right,
const vector<int> & pre, int pre_left,
unordered_map<int, int> table) {
if (in_left > in_right) {
return nullptr;
}
TreeNode* root = new TreeNode(pre[pre_left]);
int index = table[root -> value];
root -> left = helper(in, in_left, index - 1, pre, pre_left + 1, table);
root -> right = helper(in, index + 1, in_right, pre, pre_left + index - in_left + 1, table);
return root;
}Reconstruct with level order
level order 的第一个元素，一定是root。通过inorder找到root的位置，然后根据index的关系，分割左右子树。
class Solution {
public:
TreeNode* reconstruct(vector<int> in, vector<int> level) {
map<int, int> table;
for (int i = 0; i < in.size(); i++) {
table[in[i]] = i;
}
return helper(level, table);
}
TreeNode* helper(vector<int> level, map<int, int> table) {
if (level.size() == 0) {
return nullptr;
}
TreeNode* root = new TreeNode(level[0]);
int index = table[root->value];
vector<int> left;
vector<int> right;
for (int i = 0; i < level.size(); i++) {
if (table[level[i]] < index) {
left.emplace_back(level[i]);
} else if (table[level[i]] > index) {
right.emplace_back(level[i]);
}
}
root -> left = helper(left, table);
root -> right = helper(right, table);
return root;
}
};
Reconstruct Binary Search Tree With Postorder Traversal
class Solution {
public:
TreeNode* reconstruct(vector<int> post) {
//Post order -> [leftsubtree][rightsubtree]root => determine the position of root
//In order -> [left]root[right] =>recursively find left and right parts
vector<int> in(post);
sort(in.begin(), in.end());
unordered_map<int, int> table;
for (int i = 0; i < in.size(); i++) {
table[in[i]] = i;
}
return helper(in, post, table, post.size() - 1, 0, in.size() - 1);
}
TreeNode* helper(vector<int> in, vector<int> post, unordered_map<int, int> & table,
int post_right, int in_left, int in_right) {
if (in_left > in_right){
return nullptr;
}
TreeNode* root = new TreeNode(post[post_right]);
int index = table[root -> value];
root -> right = helper(in, post, table, post_right - 1, index + 1, in_right);
root -> left = helper(in, post, table, post_right - 1 - (in_right - index), in_left, index - 1);
return root;
}
};
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string order;
inorderDFS(root, order);
return order;
}
inline void inorderDFS(TreeNode* root, string& order) {
if (!root) return;
char buf[4];
memcpy(buf, &(root->val), sizeof(int)); //burn the int into 4 chars
for (int i=0; i<4; i++) order.push_back(buf[i]);
inorderDFS(root->left, order);
inorderDFS(root->right, order);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int pos = 0;
return reconstruct(data, pos, INT_MIN, INT_MAX);
}
inline TreeNode* reconstruct(const string& buffer, int& pos, int minValue, int maxValue) {
if (pos >= buffer.size()) return NULL; //using pos to check whether buffer ends is better than using char* directly.
int value;
memcpy(&value, &buffer[pos], sizeof(int));
if (value < minValue || value > maxValue) return NULL;
TreeNode* node = new TreeNode(value);
pos += sizeof(int);
node->left = reconstruct(buffer, pos, minValue, value);
node->right = reconstruct(buffer, pos, value, maxValue);
return node;
}
};
Create a Doubly Linked List from a Ternary Tree
FAQ
Difference between DFS and BFS
DFS using stacks, and BFS using queues if Non-Recursion
Difference between Recursion and Non-Recursion
Recursion is dangerous when memory resource is limited: stack may overflow; However Non-Recursion method occupies more space