--- knowledge ---
# of leaves = # of nonleaves + 1
- Binary Tree Inorder Traversal
- The point is to be done visiting all nodes in left subtree before procceding self then right tree.
- Visit self when it has no left child. Then do the same traversal on right subtree.
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> s;
TreeNode* p = root;
while (!s.empty() || p) {
while (p) {
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top();
s.pop();
ret.push_back(p->val);
p = p->right;
}
}
return ret;
}
- Binary Tree Preorder Traversal
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> s;
if (root) s.push(root);
while (!s.empty()) {
auto p = s.top();
s.pop();
if (p->right) s.push(p->right);
ret.push_back(p->val);
if (p->left) s.push(p->left);
}
return ret;
}
或者和其他统一，大家都这么写。。？
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
stack<TreeNode*> s;
TreeNode* p = root;
while (!s.empty() || p) {
while (p) {
ret.push_back(p->val);
s.push(p);
p = p->left;
}
if (!s.empty()) {
p = s.top()->right;
s.pop();
}
}
return ret;
}
- Binary Tree Postorder Traversal
Essentially for visiting a tree rooted at self, we want to visit left tree, right tree, then self->val.
- The idea here is to record self->val the second time it appears at stack top.
Think about how it works: on stack , we push self, right, left
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
stack<pair<TreeNode*, bool>> s; //snd is true when occurred on stack top
if (root) s.push(make_pair(root, false));
pair<TreeNode*, bool> p;
while (!s.empty()) {
p = s.top();
if (p.second) {
v.push_back(p.first->val);
s.pop();
} else {
s.top().second = true; // bug before, p.second is another copy, not reference
if (p.first->right) s.push(make_pair(p.first->right, false));
if (p.first->left) s.push(make_pair(p.first->left, false));
}
}
return v;
}
http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html
- 107] Binary Tree Level Order Traversal II
below essentially uses levelNum to keep track of # of nodes in last level,
or can also insert a nullptr to indicate end of each level
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(subList);
}
return wrapList;
}
}
level order, reversed : apply to last one also
void dfs(TreeNode* root, vector<vector<int>>& ret, int level) {
if (!root) return;
if (level == ret.size()) {
ret.push_back(vector<int>{});
}
ret[level].push_back(root->val);
if (root->left) dfs(root->left, ret, level+1);
if (root->right) dfs(root->right, ret, level+1);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ret{};
dfs(root, ret, 0);
return vector<vector<int>>(ret.rbegin(), ret.rend());
}
104] Maximum Depth of Binary Tree
depth is the max num of nodes from root to any leaf, so nullptr has depth of 0
1) bfs w/ nullptr as marker
// bfs
int maxDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
int dep = 0; // dep of finished level
while (1) {
auto curr = q.front();
q.pop();
if (!curr) {
++dep;
if (q.empty()) return dep;
q.push(nullptr);
} else {
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
}
return -1;
}
2) dfs using 2 stacks (THINK which 2 stacks)
int maxDepth(TreeNode* root) {
if (!root) return 0;
stack<TreeNode*> path;
stack<int> maxDep;
path.push(root);
maxDep.push(1);
int ret = -1;
while (path.size()) {
auto curr = path.top();
path.pop();
int currDep = maxDep.top();
maxDep.pop();
if (curr->left) {
path.push(curr->left);
maxDep.push(currDep+1);
}
if (curr->right) {
path.push(curr->right);
maxDep.push(currDep+1);
}
if (!curr->left && !curr->right) ret = max(ret, currDep); // technically.. but can check every time
}
return ret;
}
- 226] Invert Binary Tree
- iterative dfs simulating recursion w/ stack
TreeNode* invertTree(TreeNode* root) {
stack<TreeNode*> s;
s.push(root);
while (s.size()) {
auto curr = s.top();
s.pop();
if (!curr) continue;
s.push(curr->left);
s.push(curr->right);
swap(curr->left, curr->right);
}
return root;
}
- 100] Same Tree
how to simulate rec dfs w/ stack again
bool isSameTree(TreeNode* p, TreeNode* q) {
stack<TreeNode*> s1, s2;
s1.push(p);
s2.push(q);
while (s1.size() && s2.size()) {
auto t1 = s1.top();
auto t2 = s2.top();
s1.pop();
s2.pop();
if ((!t1) != (!t2)) return false;
if (!t1) continue;
if (t1->val!=t2->val) return false;
s1.push(t1->left);
s1.push(t1->right);
s2.push(t2->left);
s2.push(t2->right);
}
return s1.size()==s2.size();
}
235] Lowest Common Ancestor of a Binary Search Tree
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) return nullptr;
if ((p->val < root->val) && (q->val < root->val)) return lowestCommonAncestor(root->left, p, q);
if ((p->val > root->val) && (q->val > root->val)) return lowestCommonAncestor(root->right, p, q);
return root;
}
- iterative
also can use difference b/w p->val and root->val to determine relation. if the multiplication gives >0(loop again), <0, =0
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) return nullptr;
while ((!(p->val < root->val)) == (!(q->val < root->val)) ) { // invariant in loop: both in L/ both >=root
if (p->val==root->val || q->val==root->val) break; // eliminates the equal case
root = p->val < root->val? root->left : root->right;
}
return root;
}
- 101] Symmetric Tree
same trick, more practice
bool isSymmetric(TreeNode* root) {
if (!root) return true;
stack<TreeNode*> s1, s2;
s1.push(root->left);
s2.push(root->right);
while (s1.size()) {
auto t1 = s1.top(), t2 = s2.top();
s1.pop();
s2.pop();
if (!t1 && !t2) continue;
if (!t1 || !t2 || t1->val!=t2->val) return false;
s1.push(t1->left);
s2.push(t2->right);
s1.push(t1->right);
s2.push(t2->left);
}
return true;
}
- bfs using 2 qs, or just use 1 q following rule of 2n nodes nl, nr..
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> q; // always store 2n nodes, (nl, nr, ...)
q.push(root);
q.push(root);
while (q.size()) {
auto t1 = q.front();
q.pop();
auto t2 = q.front();
q.pop();
if (!t1 && !t2) continue;
if (!t1 || !t2 || t1->val!=t2->val) return false;
q.push(t1->left);
q.push(t2->right);
q.push(t1->right);
q.push(t2->left);
}
return true;
}
void dfs(TreeNode* root, vector<string>& ret, string& path) {
int oriLen = path.size();
path += to_string(root->val);
if (!root->left && !root->right) {
ret.push_back(path);
}
if (root->left) {
path += "->";
dfs(root->left, ret, path);
}
path.erase(path.begin()+oriLen+1, path.end()); // erase till last char is root->val
if (root->right) {
path += "->";
dfs(root->right, ret, path);
}
path.erase(path.begin()+oriLen, path.end());
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ret;
if (!root) return ret;
string path;
dfs(root, ret, path);
return ret;
}
Binary Tree Paths
- for string cancatenation, use += (append) for best efficiency
void dfs(TreeNode* root, vector<string>& ret, string& path) {
int oriLen = path.size();
path += to_string(root->val);
int oriLen2 = path.size();
if (!root->left && !root->right) {
ret.push_back(path);
}
if (root->left) {
path += "->";
dfs(root->left, ret, path);
}
path.erase(path.begin()+oriLen2, path.end()); // erase till last char is root->val
if (root->right) {
path += "->";
dfs(root->right, ret, path);
}
path.erase(path.begin()+oriLen, path.end());
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ret;
if (!root) return ret;
string path;
dfs(root, ret, path);
return ret;
}
- Minimum Depth of Binary Tree
- node the definition of min path: # of nodes along the shortest path from root to LEAF
int minDepth(TreeNode* root) {
if (!root) return 0;
if (!root->left || !root->right)
// because one of them is of depth 0 anyways OR l + r + 1
return 1 + max(minDepth(root->left), minDepth(root->right));
return 1 + min(minDepth(root->left), minDepth(root->right));
}
- unique binary search tree
??? read how to do q2 with dp: https://discuss.leetcode.com/topic/2940/java-solution-with-dp
int numTrees(int n) {
if (n<2) return 1;
vector<int> uniqueCt(n+1, 0);
uniqueCt[0] = uniqueCt[1] = 1;
//uniqueCt[i] stores number of unique BST that stores 1...i
for (int i=2; i<n+1; ++i) {
for (int pivot=0; pivot<=i; ++pivot) {
uniqueCt[i] += uniqueCt[pivot-1] * uniqueCt[i-pivot];
}
}
return uniqueCt[n];
}
109] Convert Sorted List to Binary Search Tree
左边n/2，右边n-n/2-1
- top to bottom, O(logn) call stack space, O(nlogn) recurse logn times, each find mid
- bottom up, time O(n); space O(logn) for callstack??
// generate BST from list using n nodes
TreeNode* genTree(ListNode*& head, int n) {
if (!n) return nullptr;
TreeNode* root = new TreeNode(-1);
root->left = genTree(head, n/2);
// assume built left tree, and head now points to current root pos
root->val = head->val;
head = head->next;
root->right = genTree(head, n-n/2-1);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
int n=0;
for (auto curr=head; curr; curr=curr->next) ++n;
return genTree(head, n);
}
- 199] Binary Tree Right Side View
- preorder traversal, keep update ret v
void preOrder(TreeNode* root, vector<int>& ret, int level) {
if (!root) return;
if (level==ret.size()) {
ret.push_back(root->val);
} else {
ret[level] = root->val;
}
preOrder(root->left, ret, level+1);
preOrder(root->right, ret, level+1);
}
vector<int> rightSideView(TreeNode* root) {
vector<int> ret;
preOrder(root, ret, 0);
return ret;
}
转念一想，直接优先traverse右树，再左。这样直接看到rightview
- 331] Verify Preorder Serialization of a Binary Tree
MARK```
- method 1: if at any point we see # # N from top to bottom of stack, trim the tree by replacing the 3 nodes with a #. using string to mock a stack
bool isValidSerialization(string preorder) {
if (preorder.empty()) return false;
preorder += ',';
string s;
char bufferc = preorder[0];
for (int i=1; i<preorder.size(); ++i) {
if (preorder[i] == ',') {
s += bufferc=='#'? '#' : 'N';
while (s.size()>=3 && s[s.size()-1]=='#' &&
s[s.size()-2]=='#' && s[s.size()-3]!='#') {
s.replace(s.end()-3, s.end(), 1, '#');
}
} else {
bufferc = preorder[i];
}
}
return s=="#";
}
- method 2:
- keep track of number of null nodes can have: should always >=0 - careful to check condition immediately after decrement by 1 on reading node
bool isValidSerialization(string preorder) {
if (preorder.empty()) return false;
int cap = 1;
char buffer;
preorder += ',';
for (int i=0; i<preorder.size(); ++i) {
if (preorder[i]==',') {
if (--cap<0) break;
if (buffer!='#') cap += 2;
} else {
buffer = preorder[i];
}
}
return cap==0;
}
- method 3:
The solution is based on the intuition that ,
`num of leaves = num of nonleaves + 1`
We should satisfy the above equation in all the process of the pre-order-traverse of the tree ....
**we just need to find the shortest prefix of the serialization sequence satisfying the property above. If such prefix does not exist, then the serialization is definitely invalid; otherwise, the serialization is valid if and only if the prefix is the entire sequence.**
```c++
bool isValidSerialization(string preorder) {
if (preorder.empty()) return false;
int numNull = 0, numNum = 0, i = 0;
char buffer;
preorder += ',';
for (; i<preorder.size() && numNull != numNum + 1; ++i) {
if (preorder[i]==',') {
if (buffer=='#') ++ numNull;
else ++ numNum;
} else {
buffer = preorder[i];
}
}
return i==preorder.size() && numNull == numNum + 1;
}
- 114] Flatten Binary Tree to Linked List
TreeNode* findTail(TreeNode* root) {
while (root && root->right) root = root->right;
return root;
}
void flatten(TreeNode* root) {
if (!root) return;
flatten(root->right);
if (root->left) {
flatten(root->left);
auto ltail = findTail(root->left);
auto tmp = root->right;
root->right = root->left;
ltail->right = tmp;
root->left = nullptr;
}
}
- 103] Binary Tree Zigzag Level Order Traversal
while dfs, use level to determine whether insert from begin/end
// levels starts with 0, and we reverse on odd level
void dfs(TreeNode* root, vector<vector<int>>& v, int level) {
if (!root) return;
if (level == v.size()) v.push_back(vector<int>{});
// reverse on odd level: add to front
if (level%2) v[level].insert(v[level].begin(), root->val);
else v[level].insert(v[level].end(), root->val);
dfs(root->left, v, level+1);
dfs(root->right, v, level+1);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> v;
dfs(root, v, 0);
return v;
}
- 106] Construct Binary Tree from Inorder and Postorder Traversal
TreeNode* build(vector<int>& inorder, int l1, int r1, vector<int>& postorder, int l2, int r2) {
if (l1>r1 || r1-l1!=r2-l2) return nullptr;
TreeNode* root = new TreeNode(postorder[r2]);
cout<<"root: "<<root->val<<" inorder range "<<l1<<"-"<<r2<<"; "<<"postorder range "<<l2<<"-"<<r2<<endl;
if (l1==r1) return root;
int inorderRoot = l1, ct=0;
for (; inorderRoot<inorder.size() && inorder[inorderRoot]!=root->val; ++inorderRoot) {
++ct;
}
// cout<<"==left: "<<"inorder range "<<l1<<"-"<<inorderRoot-1<<"; "<<"postorder range "<<l2<<"-"<<l2+ct-1<<endl;
root->left = build(inorder, l1, inorderRoot-1, postorder, l2, l2+ct-1);
// cout<<"==right: "<<"inorder range "<<inorderRoot+1<<"-"<<r1<<"; "<<"postorder range "<<l2+ct<<"-"<<r2-1<<endl;
root->right = build(inorder, inorderRoot+1, r1, postorder, l2+ct, r2-1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n1 = inorder.size();
if (postorder.size()!=n1 || !n1) return nullptr;
return build(inorder, 0, n1-1, postorder, 0, n1-1);
}
iterative DFS & BFS
- DFS:
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.prepend( currentnode.children );
//do something
}
- BFS:
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.take_first();
nodes_to_visit.append( currentnode.children );
//do something
}
