<leetcode每日一题>二叉树的LCA查找

最近正好数据结构上到二叉树，顺便把二叉树的算法给巩固了下，来到leetcode正好看到每日一题出的是二叉树的LCA问题，花了点时间完成。

首先是一颗树的LCA的定义：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

例如例子图中给出的结果可以看到，若选择值为6，4的节点的LCA，则结果为值为5的结点。

在知道了LCA的定义后，其实这道题就很显然了，因为按照二叉树的递归定义，我们只需要找出当前结点的左子树是否有题目给的结点，右子树是否有另外一个结点，就可以判断出当前结点是否是这两个结点的LCA。但是要注意一种情况，即题目给的两个结点有一个就是当前结点，另外一个在当前结点的左子树或者右子树中。所以我们可以定义lson为当前结点左子树是否包含已知结点之一，rson为当前结点右子树是否包含另外一个结点，当(lson&&rson)==true的时候说明当前结点就是要找的LCA，或者(t->val==p->val||t->val==q->val)&&(lson||rson))（t为当前结点，q和p表示已知结点，val表示结点值）为真时，说明当前结点就是LCA。

最后说明下，这个算法是自底向上查找LCA，故找到的第一个共同祖先一定是LCA。

代码如下：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode *ans;
13     bool dfs(TreeNode *t ,TreeNode *p,TreeNode *q){
14         if(t){
15             bool lson = dfs(t->left,p,q);
16             bool rson = dfs(t->right,p,q);
17             if((lson&&rson)||((t->val==p->val||t->val==q->val)&&(lson||rson))){
18                 ans = t;
19             }
20 
21             return lson||rson||(t->val==q->val||t->val==p->val);
22 
23         }
24         return false;
25     }
26     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
27         dfs(root,p,q);
28         return ans;
29     }
30 };

最后的运行结果：