golang 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2023-10-16 21:45:51

/**
 * Definition for Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Parent *Node
 * }
 */

func lowestCommonAncestor(p *Node, q *Node) *Node {
    var dfs func(*Node,*Node) bool
    dfs =func(pn *Node,qn *Node) bool{
        if pn==nil{
            return false
        }
        if pn.Val==qn.Val{
            return true
        }
        return dfs(pn.Left,qn) || dfs(pn.Right,qn)
    }
    for p!=nil{
        if dfs(p,q){
            return p
        }
        p  =p.Parent
    }
    return nil
}

python3 解法, 执行用时: 60 ms, 内存消耗: 20.5 MB, 提交时间: 2023-10-16 21:44:55

"""
# Definition for a Node.
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None
"""
class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        seen = set()
        queue = collections.deque([p, q])
        while queue:
            curr = queue.popleft()
            if curr in seen:
                return curr
            seen.add(curr)
            if curr.parent:
                queue.append(curr.parent)

java 解法, 执行用时: 28 ms, 内存消耗: 43.4 MB, 提交时间: 2023-10-16 21:44:37

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/
class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> seen = new HashSet<>();
        while (p != null) {
            seen.add(p);
            p = p.parent;
        }
        while (q != null) {
            if (seen.contains(q)) {
                return q;
            }
            q = q.parent;
        }
        return null;
    } 
}

class Solution2 {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node curP = p;
        Node curQ = q;
        while (curP != curQ) {
            curP = (curP == null) ? q : curP.parent;
            curQ = (curQ == null) ? p : curQ.parent;
        }
        return curP;
    } 
}

cpp 解法, 执行用时: 16 ms, 内存消耗: 10.4 MB, 提交时间: 2023-10-16 21:44:11

/*
// 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* point_p = p;
        Node* point_q = q;
        
        while (point_p != point_q) {
            point_p = point_p->parent ? point_p->parent : q;
            point_q = point_q->parent ? point_q->parent : p;
        }

        return point_p;
    }
};