数据结构与算法(1)支线任务4——Lowest Common Ancestor of a Binary Tree

时间:2020-12-05 07:50:17

题目如下:https://leetcode.com/problems/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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

由于题目已经给定了数据结构和函数(见下方代码部分),并不能愉快地用指向双亲的指针,然而寻找p和q两个结点的公共祖先似乎又要从下方向上找。于是我们可以考虑用递归:要找的是第一个左右孩子都是p或q祖先的结点;或者本身是p,而且是q的祖先的结点。如果符合这两点,直接返回就好;如果不是任何一个祖先,忽略掉;如果是一个的祖先,可以通过递归将这个情况返回,实现从下向上找。

代码如下:

/**
* 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 == NULL)
{
return NULL; //到了最下面,什么都没有,返回空
}
if (root == p || root == q)
{
return root; //找到了一个结点,返回该结点
} //递归
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q); if (left && right)
{
return root; //待查找结点祖先分别是左右孩子,该结点为结果
}
else if (left)
{
return left; //只是一个的祖先,将结果“上传”
}
return right;
}
};

没时间了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

//以下不是2015年11月23日00:00前写的

//然而为保持风格还算统一,还是想加几篇觉得写得不错的博客

附:

http://arsenal591.blog.163.com/blog/static/253901269201510169448656

http://www.cnblogs.com/ocNflag/p/4967695.html

http://blog.sina.com.cn/s/blog_1495db3970102w4wl.html

http://www.cnblogs.com/fighter-MaZijun/p/4979318.html

http://www.cnblogs.com/lqf-96/p/lowest-common-ancestor-of-a-binary-tree.html

再附://有图似乎比我上面写的一坨还是更直观一些

http://www.cnblogs.com/Jueis-lishuang/p/4984971.html

最后的最后:

本来此处想装得有文采一些,写一些现在只想好一半的东西,然而写不写出来对我个人似乎意义不大。//这周似乎也有些忙

感叹两句就好了:

大神似乎与咸鱼们并不是同一种生物

算了……就这一句也够了……