Question

如何计算两个节点的公共父节点到两个节点的最小距离

Answer 1

由于有父节点指针，这道题目的难度一下子就降低了许多。
思路一：我们首先找到两个节点的高度差，然后从较靠近根结点的一层开始向上找，若父节点为同一节点则该节点为解。
int getHeight(TreeNode *node) {
int height = 0;
while (node) {
height++;
node = node->parent;
}
return height;
}

TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second) {
int height1 = getHeight(first), height2 = getHeight(second), diff = height1 - height2;
if (diff < 0) {
diff = -diff;
while(diff--) {
second = second->parent;
}
} else {
while(diff--) {
first = first->parent;
}
}
while (first != second) {
first = first->parent;
second = second->parent;
}
return first;
}

思路二：若允许浪费空间，那么可以用两个Stack来存储从first和second到根结点的各个节点，然后出栈时比较地址是否一致，最后一个地址一致的节点为解。