LeetCode //C - 236. Lowest Common Ancestor of a Binary Tree

发布时间:2024年01月18日

236. Lowest Common Ancestor of a Binary Tree

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.

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.

Example 3:

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

Constraints:
  • The number of nodes in the tree is in the range [ 2 , 1 0 5 ] [2, 10^5] [2,105].
  • ? 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 ?109<=Node.val<=109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

From: LeetCode
Link: 236. Lowest Common Ancestor of a Binary Tree


Solution:

Ideas:
  1. If the current root is NULL, return NULL as we’ve reached the end of a path without finding either p or q.
  2. If the current root is either p or q, then the current root is the LCA because by the problem’s definition, a node can be a descendant of itself.
  3. Recursively search for p and q in the left and right subtrees of the current root.
  4. If both left and right recursive calls return non-NULL values, it means we’ve found p and q in different subtrees of the current root, so the current root is the LCA.
  5. If only one of the recursive calls returns a non-NULL value, this means that both p and q are found in one subtree, and the non-NULL node is the LCA.
  6. If both left and right are NULL, p and q were not found under this root, so we return NULL.
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    // If looking at a null node, return null
    if (root == NULL) return NULL;

    // If either p or q is the root, then the root is the LCA
    if (root == p || root == q) return root;

    // Recursively call the function on the left and right child
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // If both left and right are not null, we found our LCA
    if (left != NULL && right != NULL) return root;

    // If one of the children returned a node, meaning either p or q was found on left or right subtree.
    // If neither was found, then this root can't be LCA
    return left != NULL ? left : right;
}
文章来源:https://blog.csdn.net/navicheung/article/details/135664465
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。