题目

来源：牛客算法
地址：https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=117&&tqId=37826&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking

1.描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
注：本题保证二叉树中每个节点的val值均不相同。
如当输入[3,5,1,6,2,0,8,#,#,7,4],5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：
所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

2.示例

• 示例1

输入：
[3,5,1,6,2,0,8,#,#,7,4],5,1
返回值：
3

解题思路

该题可以使用深度优先搜索解决。
1.进行一次深度优先搜索建立从根节点到p节点的路径；
2.从路径末尾开始倒叙遍历路径，判断路径节点是否为q的祖先节点，若是，则该节点就是pq最近的祖先节点。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p->val, 1);//创建根节点到p节点的路径
        for(int i = visited.size()-1; i >= 0; i--){//从p节点开始倒着遍历根节点到p的路径
            if(dfs(visited[i],q->val, 0)) return visited[i];//若该节点为q的祖先节点，则返回该节点
        }
        return visited[0];//返回根节点
    }

    bool dfs(TreeNode* root, int o1, bool isModifyVector){//深度优先搜索
        if(root==NULL) return false;//根节点为空，返回假
        if(root->val == o1){//若根节点为目标节点
            if(isModifyVector)//先判断是否记录路径
            visited.push_back(root);//并根据isModifyVector创建路径
            return true;//返回真
        }
        else{//若根节点不为目标节点，继续遍历非空子节点
            if(isModifyVector)
            visited.push_back(root);
            if(root->left && dfs(root->left, o1, isModifyVector)) return true;//若左子节点为目标节点祖先，返回真
            if(root->right && dfs(root->right, o1, isModifyVector)) return true;//若右子节点为目标节点祖先，返回真
            if(isModifyVector)
            visited.pop_back();
            return false;//左右子节点都不是目标节点的祖先节点，返回假
        }
    }

    vector<TreeNode*> visited;//存储路径
};

复杂度分析

时间复杂度： O(N)。N为二叉树节点数，深度优先搜索的时间消耗。
空间复杂度： O(N)。存储根节点到p节点路径的空间消耗。

更多知识内容分享：
牛客个人主页https://blog.nowcoder.net/newcoderthewarrior
CSDN个人主页https://blog.csdn.net/qq_39255924