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]

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.

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

题意:给出一棵二叉树上的两个节点,返回他们的最近公共祖先

对于节点P、节点Q,他们的位置关系大概有两种,也分别对应了最近公共祖先的两种情况
1.两个节点在某个节点R的同一棵子树上,那么最近公共祖先就是两个节点中深度较浅的节点
2.两个节点在某个节点R的不同子树上,那么最近公共祖先就是R
(节点R一定是满足上述两个条件之一的最深的节点)

所以我们在左子树和右子树上递归寻找

如果发现当前节点就是节点P或节点Q,那么由于我们还未找到另一个节点,下一步操作是在当前节点的左右子树上再去找,说明满足了上述第一个情况

如果发现在当前节点的左右子树分别找到了两个节点,满足上述第二个情况,当前节点就是LCA,返回

代码如下:

LCA可以应用于计算二叉树任意两个节点的最短距离,应用公式$depth_p + depth_q – 2 * depth_{LCA}$(depth表示节点的深度,该公式易得)

代码如下:

发表评论

电子邮件地址不会被公开。