236、二叉树的最近公共祖先

前提：

• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

代码如下：

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

注意点：

1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。

2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

形象化表示就是从root节点开始派出左右两个侦察兵，先判断他们是不是目标值，如果不是就让他们各自在探查自己的左右两个侦察兵是不是，不是就接着递归，直到有一个找到了目标值，就将找到这个目标值的侦察兵的信息记录一层一层传递回来，若有一个节点的左右侦察兵同时接到了探查信息，就将这个节点逐级返回。