1650. Lowest Common Ancestor of a Binary Tree III

Problem Statement

link: LeetCode.cn LeetCode Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node { public int val; public Node left; public Node right; public Node parent; } According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example:

Input: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5

Input: root = [1,2], p = 1, q = 2 Output: 1

Constraints: The number of nodes in the tree is in the range [2, 105]. -109 <= Node.val <= 109 All Node.val are unique. p != q p and q exist in the tree.

Solution Approach

Algorithm

Complexity

time complexity: O(h) space complexity: O(h)

Implement

    class Solution: def lowestAncestor(self, p: Node, q: Node)-> Node:
    def helper(root, node): 
        if not root:
            return False
        if root == node:
            return True
        return helper(root.left, node) or helper(root.right, node)

    if p == q:
        return p
    if p.parent == q.parent: 
        return p.parent
    if helper(p, q): 
        return p
    if helper(q, p): 
        return q
    return self.lowestAncestor(p.parent, q.parent) 

    
    

Twitter  facebook  Email