023.二叉树的最近公共祖先

题目链接：

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

大概思路：

题目要求：

给定一个二叉树, 找到该树中两个指定节点q，p的最近公共祖先x。（q、p一定存在且值不同）

最近公共祖先：

两个节点共同的祖先，同时深度尽可能大（其中一个可以是祖先本身）

思路：

q，p的最近公共祖先有两种情况

第一种：

思路就是从底向上遍历，遇见q、p返回其值，返回的过程中，

如果某节点最先接收左右子树的q、p，则该节点是最小节点，返回该节点直至root，

但如果没有某节点接受到q，p，那么root一定接受到p or q ，此时p or q为最小节点(这是第二种情况)（题目要求p，q必须存在，且值不一致）

第二种：

这种情况的思路，遍历的途中，p会被忽略，但返回了q上去，而此时q是最近公共祖先，所以情况被包含到第一种情况的代码里了

递归三部曲：

1.确定递归函数参数和返回类型：

参数为根节点，但因为需要返回q，p的值在递归过程中，所以加两个树指针q，p，同时返回类型为树指针

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);

判断就是左右为不为空三种情况返回，

• 左右不为空，为最近祖先，返回该节点上去
• 左空右不空，返回right
• 左不空右空，返回left
• 左右为空，该值不是祖先，返回null上去

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;

4.总代码：

就是遍历寻找q、p，然后返回值的过程中交给中判断是否为最近祖先，如果没判断出来（只有一个nell和一个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;
        }

    }
};

个人想法：

感觉没连起来啊，第二次写再看看。