二叉树——二叉树的最近公共祖先

前言题目思路代码结论

解决公共祖先问题时我想到的办法时两次遍历，分别在树tree中遍历p和q，
两次的遍历中从根到目标节点的路径节点指针的值分别保存到集合和队列中，
在队列出队时只要在集合中出现过，那他就是最近公共祖先。
这个方法也能AC。但是时间和空间消耗巨大。
借鉴了一下精选接法，才明白对于二叉树的递归还是内有熟练应用。

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5

解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xopaih/
来源：力扣（LeetCode）

利用递归会所，把遍历到的结点返回一个结点指针，如果左右孩子或本身是p或者q的路径，把该结点的指针值返回；若不是，就返回空结点指针；
需要注意的是：存在下面两种情况：
1、如果p或者q就是最近公共祖先结点node，则函数在node的路径就不向下继续寻找另外一个结点（此时另外路径上找不到另一个目标结点），这个时候就会出现left == null或者right == null的情况（见题解代码）。则会有return left ? left : right;的返回值，从该节点向上的返回值一致是此公共祖先；
2、不满足第一种情况的话，就会存在一个结点的左孩子和右孩子分别分布p和q的路径，此时就是left!=NULL同时right!= NULL。通过条件判断if(left&&right)来确定该节点向上回溯都返回该结点。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) 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;
        return left ? left : right;      
    }
};

二叉树的递归入门在前中后序遍历，之后理解“自顶向下”和“自底向上”的递归方向的选择后，也要开始了解带返回值的递归。
要区分递归过程中修改树和不修改书，其实和带不带返回值没什么影响，不要在考虑太多的情况下，反而把很多东西混淆，复杂化！！

祝勇攀高峰！一番风顺！！