给定一棵二叉树，找到树中两个指定节点的最近公共祖先。示例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解题思路首先，本题的函数签名如下：TreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq);rootnode确定一棵二叉树，p和q是这棵二叉树上的两个节点，让你返回p节点和q节点最近的公共祖先节点。所有二叉树的套路都是一样的，可以先把遍历框架写出来：//中序遍历TreeNoderight=lowestCommonAncestor(root.right,p,q);//后序遍历}现在我们考虑如何添加一些细节，将框架转化为解决方案。遇到任何递归问题，无非就是三个灵魂问题：1、这个函数是干什么用的？2、这个函数参数中的变量是什么？3.你应该怎么做才能得到函数的递归结果？类似于动态规划的思想，同样需要明确定义“定义”、“状态”和“选择”1）这个函数是做什么用的？描述lowestCommonAncestor函数的“定义”。说明：向该函数输入三个参数root、p、q，返回一个节点。情况1，如果p和q都在以root为根的树中，则函数返回p和q最近的公共祖先节点。在情况2中，如果p和q都不在以root为根的树中，那么当然会返回null。在情况3中，如果以root为根的树中仅存在p和q之一，则函数返回该节点。题目说输入的p和q一定存在于root-rootedtree中，但是在递归过程中，可能会出现以上三种情况，所以这里需要定义清楚，后面的这些定义都会在代码中体现出来2）这个函数的参数中，变量是什么？描述这个函数的“状态”。说明：函数参数中的变量为root，因为根据框架，lowestCommonAncestor(root)会递归调用root.left和root.right；至于p和q，我们要求他们有共同的祖先，他们肯定不会改变。它在递归过程中逐层传递。你也可以理解为这是“状态传递”，每次递归都在做什么？不就是把“根作为根”改为“根的子节点作为根”来不断缩小问题的规模吗？3）得到函数的递归结果，怎么办？得到递归调用的结果后，你会做什么“选择”？首先考虑基本情况，如果根为空，则必须返回null。如果root本身是p或q，比如root是p节点，如果q存在于以root为根的树中，显然root是最近的共同祖先；即使以root为根的树中不存在q，根据情况3的定义也应该返回根节点。上面两种情况的basecase可以填写框架代码：TreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){//Ifrootisemptyif(root==null)returnnull;//如果root本身是p或qif(root==p||root==q)returnroot;TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);}现在对递归调用的左右结果做一些事情。根据刚才第一个问题的函数定义，我们继续分case讨论：case1，如果p和q都在根树中，那么left和right一定分别是p和q（来自basecasefrom).情况2，如果p和q都不在以root为根的树中，则直接返回null。在情况3中，如果以root为根的树中仅存在p和q之一，则函数返回该节点。理解了以上三点后，就可以直接看解法代码了：如果（root==p||root==q）返回root；TreeNodeleft=lowestCommonAncestor(root.left,p,q);TreeNoderight=lowestCommonAncestor(root.right,p,q);//情况1if(left!=null&&right!=null){returnroot;}//情况2if(left==null&&right==null){returnnull;}//Case3returnleft==null?右左;}}个人理解：在查找前序位置的节点，如果是空节点，直接返回，如果找到p或者q，则返回该节点，否则继续递归，接收到前序位置的返回值后序位置，如果left和right都不为空，分别表示p和q，当前根是最近的共同祖先，直接返回根节点。如果一个为空，另一个不为空，则说明找到了一个结点，将该结点向上传递寻找另一个结点，直到两个都不为空为止。此时根为最近的共同祖先，直接返回根节点。对于case1，你肯定有疑惑，left和right非空，分别是p和q，可以说明root是他们的共同祖先，但是你能确定root是“最近”的共同祖先吗？这是一个巧妙的地方，因为这里是二叉树的后序遍历！前序遍历可以理解为从上到下，后序遍历是从下到上，就像从p和q开始往上走一样。第一个相交节点是根。你认为这是最近的共同祖先吗？羊毛布？
