遇到一些题目, 用递归加 bottom-up 解法能得到更优的时间复杂度, 对这些题目做一个汇总
1. google code jam Rational Number Tree
2. 二叉树的公共祖先节点
3. leetcode convert sorted list to balanced search tree
1. Rational Number Tree
void getPQ(int n, int &p, int &q) {
if(n == 1) {
p = q = 1;
return ;
}
getPQ(n/2, p, q);
int newp, newq;
if(n & 1) { /* 右孩子 */
newp = p + q;
newq = q;
}else {
newp = p;
newq = p + q;
}
p = newp;
q = newq;
}
void getN(int &n, int p, int q) {
if(p == 1 && q == 1) {
n = 1;
return;
}
int newp, newq;
if(p > q) { /* 右孩子 */
newp = p - q;
newq = q;
getN(n, newp, newq);
n = n*2 + 1;
}else {
newp = p;
newq = q-p;
getN(n, newp, newq);
n = n*2;
}
}
2. 二叉树的公共节点
Node* LCA(Node *root, Node *p, Node *q) {
if(root == NULL) return NULL;
if(p == root || q == root) return root;
Node* lchild = LCA(root->left, p, q);
Node* rchild = LCA(root->right, p, q);
if(lchild && rchild) return root;
if(lchild) return lchild;
return rchild;
}
3. Convert Sorted List to Balanced Search Tree
TreeNode* buildTree(ListNode* &head, int st, int ed) { if(st > ed) return NULL; int mid = (st+ed)>>1; TreeNode* lchild = buildTree(head, st, mid-1); TreeNode* parent = new TreeNode(head->val); head = head->next; TreeNode* rchild = buildTree(head, mid+1, ed); parent->left = lchild; parent->right = rchild; return parent; }