二叉树的最近公共祖先
    题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
    图片.png

    思路：构造递归判断节点是否在子树的辅助函数，然后主函数递归：

    • 若root就是其中一个节点，返回root
    • 若两个节点分别在root的左右子树，返回root
    • 若两个节点在root的同一侧，root赋值为该子树root，重复该过程

    参考代码：

    1. class Solution {
    2. public:
    3.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    4.         while (root != NULL) {
    5.             if (root->val == p->val || root->val == q->val) {
    6.                 return root;
    7.             }
    8.             if (isInSubTree(root->left, p)) {
    9.                 if (isInSubTree(root->left, q)) {
    10.                     root = root->left;
    11.                     continue;
    12.                 }
    13.                 else {
    14.                     return root;
    15.                 }
    16.             }
    17.             else if (isInSubTree(root->right, p)) {
    18.                 if (isInSubTree(root->right, q)) {
    19.                     root = root->right;
    20.                     continue;
    21.                 }
    22.                 else {
    23.                     return root;
    24.                 }
    25.             }
    26.         }
    27.         return root;
    28.     }
    29.     bool isInSubTree(TreeNode* root, TreeNode* n) {
    30.         if (root == NULL) {
    31.             return false;
    32.         } 
    33.         if (root->val == n->val) {
    34.             return true;
    35.         }
    36.         return isInSubTree(root->left, n) || isInSubTree(root->right, n);
    37.     }
    38. };