二叉搜索树
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 如果p、q一定存在，那么root就一定不是空指针
TreeNode* traverse = root;
while (true) {
if (p->val < traverse->val && q->val < traverse->val) traverse = traverse->left;
else if (p->val > traverse->val && q->val > traverse->val) traverse = traverse->right;
else if (p == traverse) return p;
else if (q == traverse) return q;
else return traverse;
}
}
二叉树
递归自底向上，返回每一个节点下面（包括）自己有没有目标节点之一
- 有就返回子节点指针（最开始肯定是返回自己的指针）
- 没有就返回空指针
- 左右节点都各自包含一个就找到了
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
TreeNode* leftHas = lowestCommonAncestor(root->left, p, q);
TreeNode* rightHas = lowestCommonAncestor(root->right, p, q);
if ((leftHas && rightHas) || root == p || root == q) return root;
if (leftHas) return leftHas;
else return rightHas;
}
任意树
由于 力扣 平台本身的限制，书中的最后一问没有体现出来——对于任意树
书中给出的思路是这样的：
- 遍历整棵树并构造出两条从根节点到目标节点的链表
- 查找链表的最后一个公共节点
对于 1 可以采用一种回溯的做法，另外就是这里不需要真的去构建一条链表，因为其实是从已经一一指向的路径中挑选一条就可以了，所以其实用数组也是可以的
对于 2 很简单，双指针
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> list1, list2;
findPath(list1, p,root);
findPath(list2, q,root);
TreeNode* res = nullptr;
for (int i = 0; i < min(list1.size(), list2.size()); i++) {
if (list1[i] == list2[i]) res = list1[i];
else break;
}
return res;
}
bool findPath(vector<TreeNode*> &list, TreeNode* target,TreeNode* root) {
if (!root) return false;
list.push_back(root);
if (list.back() == target) return true;
if (findPath(list, target, root->left) || findPath(list, target, root->right)) {
return true;
}
list.pop_back();
return false;
}