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

describe

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes P and Q as The lowest node in T that has both P and Q as Descendants where we allow a node to be a descendant of itself.”

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

Example 2:

Input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.Copy the code

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1
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 a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to Wikipedia LCA: The lowest common ancestor is defined as the lowest node between two nodes P and Q, i.e. the node in T that has both P and Q as descendants (we allow a node to be its own descendant). After looking at a few examples, you should understand what LCA means. The easiest way to solve this problem is to find the path from the root node to P and the path from the root node to Q, and then find the bifurcated node, which is LCA. But the time complexity of this solution is to find p or Q. The time complexity is O(n). The space is going to be order logn.

answer

class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ result = [] def dfs(root, path, target): if not root: return if root.val == target.val: path.append(root.val) result.append(path) if root.left: dfs(root.left, path+[root.val], target) if root.right: dfs(root.right, path+[root.val], target) dfs(root, [], p) dfs(root, [], q) p_path = result[0] q_path = result[1] idx = 0 while idx < min(len(p_path), len(q_path)): if p_path[idx] ! = q_path[idx]: return TreeNode(p_path[idx-1]) idx += 1 return TreeNode(p_path[idx-1])Copy the code

The results

Runtime: Linked to the linked node in the linked list. Memory Usage: In the linked list, submissions are linked to the linked list in the linked list.Copy the code

parsing

In addition, we can define DFS as how many p’s or q’s are contained in a subtree, and return 0 if there is no P or Q, 1 if there is only any p or Q, and 2 if there are both. Because we recurse from the top down, we return results from the bottom up, so the first time we encounter a node where DFS returns 2, it must be LCA.

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, the molecular weight for each node in the linked list is given in the linked list. The linked submissions in the linked list are linked to the linked list in the linked list.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation