1650. Lowest Common Ancestor of a Binary Tree III

一刷 05/2022

Version #1 Two Pointers

Time O(Depth P + Depth Q)

Space O(1)

Runtime: 41 ms, faster than 34.07% of Java online submissions for Lowest Common Ancestor of a Binary Tree III.

Memory Usage: 47.3 MB, less than 53.85% of Java online submissions for Lowest Common Ancestor of a Binary Tree III.

 /*

// 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) {

        Node pointerP = p, pointerQ = q;

        while (pointerP != pointerQ) {

            pointerP = pointerP == null ? q : pointerP.parent;

            pointerQ = pointerQ == null ? p : pointerQ.parent;

        }

        return pointerP;

    }

}