4.1] 实现一个函数，检查二叉树是否平衡。（任二子树高度差不超过一）
depth of tree node: # edges from root to node
height of tree node: #edges from note to deepest leaf
but, depth of tree == height of tree
Balanced Binary Tree
4.2] 给有向图，找出两个节点之间是否存在路径
- dfs: easy to write w/ recursion
- bfs: iterative, more efficient to check shortest path
4.3] 给定一个有序整数数组，元素各不相同且按照升序排列，编写一个算法，创建一个高度最小的二叉查找树
=========================================
btw
- Binary Search Tree Iterator
- how to think of using stack?
- subtle point, how to update precisly when
next()is called
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
pushAll(root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
}
/** @return the next smallest number */
int next() {
auto node = s.top();
s.pop();
if (node->right) pushAll(node->right);
return node->val;
}
private:
stack<TreeNode*> s;
void pushAll(TreeNode* root) {
while (root) {
s.push(root);
root = root->left;
}
}
};
/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
4.4】 给定一棵二叉树，设计一个算法，创建含有某一深度上所有结点的链表(比如：若一棵树的深度为D,则会创建出D个链表）
- any traversal, just MEMO LEVEL!
- bfs
4.5] Validate Binary Search Tree
bool validateTree(TreeNode* root, TreeNode*& last) {
if (!root) return true;
if (!validateTree(root->left, last)) return false;
if (last && root->val <= last->val) return false;
last = root;
return validateTree(root->right, last);
}
bool isValidBST(TreeNode* root) {
TreeNode* last = nullptr;
return validateTree(root, last);
}
4.7] Lowest Common Ancestor of a Binary Tree
- O(n)
bool cover(TreeNode* root, TreeNode* target) {
if (!root) return false;
if (root==target) return true;
return cover(root->left, target) || cover(root->right, target);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (root==p || root==q) return root;
auto lhasp = cover(root->left, p);
auto lhasq = cover(root->left, q);
// both at left
if (lhasp && lhasq) return lowestCommonAncestor(root->left, p, q);
// only one at left
if (lhasp || lhasq) return root;
// none at left
return lowestCommonAncestor(root->right, p, q);
}
- optimized (assume p, q in tree)
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
if (root==p || root==q) return root;
auto searchl = lowestCommonAncestor(root->left, p, q);
auto searchr = lowestCommonAncestor(root->right, p, q);
if (searchl && searchl!=p && searchl!=q) return searchl; // found at lt
if (searchr && searchr!=p && searchr!=q) return searchr; // found at rt
if (searchl && searchr) return root;
// else if (root==p || root==q) return root;
else return searchl? searchl : searchr;
return nullptr;
