Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes p and q. if either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.According to the definition of LCA on Wikipedia: The lowest common ancestor of two nodes p and q in a binary 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), A desendant of a node x is a node y that is on the path from node x to some leaf node.

Example 1:

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.Copy the code

Note

The number of nodes in the tree is in the range [2, 10^5]. -10^9 <= Node.val <= 10^9 All Node.val are unique. p ! = q p and q will exist in the tree.Copy the code

parsing

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes P and q. If there is no node P or q in the tree, null is returned. They’re going to make sure that all the values of the nodes in the tree are unique.

276. Lowest Common Ancestor of a Binary Tree 236. Lowest Common Ancestor of a Binary Tree

answer

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def __init__(self):
        self.result = None
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        def dfs(root, p, q):
            if not root: return 0
            left = dfs(root.left, p, q)
            right = dfs(root.right, p, q)
            self_ = 1 if (p == root or q == root) else 0
            count = left + right + self_
            if count == 2 and not self.result:
                self.result = root
            return count
        dfs(root, p, q)
        return self.result
        	      
		
Copy the code

The results

Runtime: In the linked list, molecular molecular evolution in the linked list is given in the linked list. The linked submissions in the linked list are linked to each node in the linked list.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation