题目描述

Variation of 160. Intersection of Two Linked Lists

样例

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

算法1 (Two Pointers)

时间复杂度: $O(h_1 + h_2)$

where $h_1$ and $h_2$ are the heights of nodes $p$ and $q$.

空间复杂度: $O(1)$

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        Node *a = p;
        Node *b = q;
        while (a != b) {
            a = a == nullptr ? q : a->parent;
            b = b == nullptr ? p : b->parent;
        }
        return a;
    }
};