236. Lowest Common Ancestor of a Binary Tree
Medium
14.1K
331

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, 105]`.
• `-109 <= Node.val <= 109`
• All `Node.val` are unique.
• `p != q`
• `p` and `q` will exist in the tree.
Accepted
1.3M
Submissions
2.2M
Acceptance Rate
59.1%

Seen this question in a real interview before?
1/4
Yes
No

Discussion (0)

Related Topics
{"ft_lang_label":"__label__en","ft_lang_prob":0.86960423,"math_prob":0.98704743,"size":804,"snap":"2023-14-2023-23","text_gpt3_token_len":273,"char_repetition_ratio":0.10375,"word_repetition_ratio":0.102564104,"special_character_ratio":0.35945272,"punctuation_ratio":0.23660715,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99192274,"pos_list":[0,1,2,3,4],"im_url_duplicate_count":[null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-05T01:01:39Z\",\"WARC-Record-ID\":\"<urn:uuid:60eafd84-416e-4677-a083-62ab686d8331>\",\"Content-Length\":\"166820\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a761d92e-c3e4-4558-b930-575f87c052ce>\",\"WARC-Concurrent-To\":\"<urn:uuid:cce755ae-2bed-4819-b6e7-a4ff5acc33f5>\",\"WARC-IP-Address\":\"172.67.72.213\",\"WARC-Target-URI\":\"https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/?ref=laigary.com\",\"WARC-Payload-Digest\":\"sha1:DUVR3PI67VT6IACSWHPAABQ7LCVOZAML\",\"WARC-Block-Digest\":\"sha1:HITGW4J4JRQBDQDFOT3OJAJEGDN6DSBW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224650409.64_warc_CC-MAIN-20230604225057-20230605015057-00791.warc.gz\"}"}