一、题意
二、解答过程
**思路/方法：**该题用到自底向上查找------回溯！还要用到递归！
如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
使用后序遍历，回溯过程，就是从低向上遍历节点，一旦发现这个条件的节点，就是最近公共节点。
- 先找节点路径p和q
- 在结点路径的最近公共祖先节点
递归三部曲里的逻辑处理：
// //3.遍历整棵树 TreeNode *left=lowestCommonAncestor(root->left,p,q); TreeNode *right=lowestCommonAncestor(root->right,p,q);
递归函数有返回值时：
- 搜索一条边：
if (递归函数(root->left)) return ; if (递归函数(root->right)) return ;
- 搜索整棵树：
left = 递归函数(root->left); right = 递归函数(root->right); left与right的逻辑处理;
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）
class Solution { public://1. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { //2.如果找到了节点p或者节点q或者遇到了空节点。就返回 if(root==q||root==p||root==NULL) return root; //3.遍历整棵树 TreeNode *left=lowestCommonAncestor(root->left,p,q);//不断遍历左子树 TreeNode *right=lowestCommonAncestor(root->right,p,q);//不断遍历右子树 //讨论情况： if(left!=NULL&&right!=NULL) return root; if(left==NULL&&right!=NULL) return right; else if(left!=NULL&&right==NULL) return left; else{//left==NULL&&right==NULL return NULL; } } };
