首页 > 代码库 > Lowest Common Ancestor of a Binary Tree, with Parent Pointer
Lowest Common Ancestor of a Binary Tree, with Parent Pointer
Given a binary tree, find the lowest common ancestor of two given nodes in tree. Each node contains a parent pointer which links to its parent.
int getHeight(Node* p){ int height = 0; while (p) { height++; p = p->parent; } return height;}Node* LCA(Node* p, Node *q){ int h1 = getHeight(p); int h2 = getHeight(q); if (h1 > h2) { swap(h1, h2); swap(p, q); } for (int h = 0; h < h2-h1; h++) { q = q->parent; } while (p && q) { if (p == q) return p; p = p->parent; q = q->parent; } return NULL;}
Lowest Common Ancestor of a Binary Tree, with Parent Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。