Skip to content

Latest commit

 

History

History
139 lines (86 loc) · 4.03 KB

0236-lowest-common-ancestor-of-a-binary-tree.adoc

File metadata and controls

139 lines (86 loc) · 4.03 KB

236. Lowest Common Ancestor of a Binary Tree

{leetcode}/problems/lowest-common-ancestor-of-a-binary-tree/[LeetCode - 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).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

{image_attr}

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.

Note:

  • All of the nodes' values will be unique.

  • p and q are different and both values will exist in the binary tree.

思路分析

D瓜哥的思路：先找出一条从根节点到某个节点的路径；然后从这条路径上以此去寻找另外一个节点。找到这返回此节点。

思考题：如何按照"路径"的思路实现一遍？

这道题是 235. Lowest Common Ancestor of a Binary Search Tree 的延伸。但是，解题思路略有不同，本体的解题思路也可用于前者。

有两种情况：

  1. 两个节点是一个树下的两个节点；

  2. 一个节点就是另外一个节点的祖先节点；

根据这两点，针对一棵树进行递归遍历，去寻找当前节点与两个指定节点相等的节点，找到就返回当前节点（也就是两个节点其中之一），找不到就返回 null。

当左右子树都返回不为 null 时，那么当前节点就是两棵树的公共祖先节点。情况如下：

{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
一刷
link:{sourcedir}/_0236_LowestCommonAncestorOfABinaryTree.java[role=include]
二刷
link:{sourcedir}/_0236_LowestCommonAncestorOfABinaryTree_2.java[role=include]
三刷
link:{sourcedir}/_0236_LowestCommonAncestorOfABinaryTree_3.java[role=include]