leetcode:236. The nearest common ancestor of binary tree

236. The nearest common ancestor of a binary tree

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .

In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Example 1：

 Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 Output ：3
 explain ： node  5  And nodes  1  The most recent public ancestor of is the node  3 .

Example 2：

 Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 Output ：5
 explain ： node  5  And nodes  4  The most recent public ancestor of is the node  5 . Because by definition, the nearest common ancestor node can be the node itself .

Example 3：

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

Tips ：

• The number of nodes in the tree is in the range [2, $10^5$] Inside .
• $-10^9$ <= Node.val <= $10^9$
• all Node.val Different from each other .
• p != q
• p and q All exist in a given binary tree .

solution

• recursive : Start with the root node , If the root node is empty , Or a search element is the root node , Directly back to the root node ; Then recursively find the left subtree , Right subtree , If the search results of both subtrees are not empty , indicate p,q The two elements to be found are the same as the root node of the left subtree or the root node of the right subtree , Then the common node of the two is the root node of the tree ; If the search of a subtree is empty , Then return the search result of another subtree ;

Code implementation

recursive

python Realization

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
           return root
        
        if root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:  #  The search results of the two subtrees are not empty , Description shot ,
            return root

        return left if left else right

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if (root == nullptr)
            return root;
        
        if (p == root || q == root)
            return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != nullptr && right != nullptr)
            return root;
        
        return left != nullptr ? left : right;

    }
};

Complexity analysis

• Time complexity ： $O(N)$
• Spatial complexity ： $O(N)$