236. Lowest Common Ancestor of a Binary Tree

Problem Statement

link: LeetCode.cn LeetCode

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example:

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

Solution Approach

method1

Utilizes recursive traversal to identify the lowest common ancestor by exploring the binary tree from the root downward.

method2

Finds paths from the root to the given nodes and then determines their lowest common ancestor by iterating over these paths.

Algorithm

method1

This method utilizes a recursive approach to traverse the binary tree. It starts from the root and recursively explores the left and right subtrees. If either of the given nodes p or q is found, the current node is returned. If both p and q are found in different subtrees, the current node is the lowest common ancestor (LCA). If both nodes are found in the same subtree, the process continues until the LCA is found.

method2

This method involves finding paths from the root to nodes p and q using DFS. It traverses the tree twice to find paths for both nodes. Once paths for both nodes are obtained, it iterates over the paths simultaneously. The last common node before paths diverge is considered the lowest common ancestor (LCA). This method offers an alternative approach by explicitly finding paths to nodes and then identifying the LCA.

Implement

    # Definition for a binary tree node. class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution: #method 1
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      if not root or root == q or root == p:
          return root

      left = self.lowestCommonAncestor(root.left, p, q)
      right = self.lowestCommonAncestor(root.right, p, q)
      if not left: return right
      if not right: return left
      return root

#method 2
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def findPath(root, target, path):
            if root is None:
                return False
            path.append(root)
            if root == target:
                return True
            if (findPath(root.left, target, path) or findPath(root.right, target, path)):
                return True
            path.pop()
            return False

        p_path = []
        q_path = []
        findPath(root, p, p_path)
        findPath(root, q, q_path)
        
        lca = None
        for i, j in zip(p_path, q_path):
            if i == j:
                lca = i
            else:
                break
        
        return lca
      

    
    

Twitter  facebook  Email