leetcode 二叉树的公共近祖先

思路：
遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。

那么二叉树如何可以自底向上查找呢？

回溯啊，二叉树回溯的过程就是从低到上。

后序遍历就是天然的回溯过程，最先处理的一定是叶子节点。

接下来就看如何判断一个节点是节点q和节点p的公共公共祖先呢。

如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。

使用后序遍历，回溯的过程，就是从低向上遍历节点，一旦发现如何这个条件的节点，就是最近公共节点了。

递归三部曲：
1.确定递归函数的返回值及其参数
2.确定递归终止条件
3.确定单层递归的逻辑

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
      if(q==root||p==root||root==NULL) return root;
      TreeNode*left=lowestCommonAncestor(root->left,p,q);//遍历左子树
      TreeNode*right=lowestCommonAncestor(root->right,p,q);//遍历右子树
        if(left!=NULL&&right!=NULL) return root;
      else if(left!=NULL&&right==NULL) return left;
        else if(right!=NULL&&left==NULL) return right;
        else
        {
            return NULL;
        }
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结：
1.求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
2.在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
3.要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

如有错误，多多指教！