NC102_在二叉树中找到两个节点的最近公共祖先

知识点：二叉树、递归
题目链接

题目描述
给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

示例1
输入： [3,5,1,6,2,0,8,#,#,7,4],5,1
输出： 3

解题思路

1. 这里需要用到递归 递归查询两个给定的结点o1 和 o2
2. 如果当前节点 是空的 则返回 如果是o1 或者 o2 也返回本身
3. 类似于后序遍历 往左边去找 往右边去找
4. 如果左边和右边都不存在 要找的节点返回-1
5. 如果左边有 或者 右边有 就是单边存在的情况 把这个情况返回 告诉上面的节点 在下面可以找到你要的节点
6. 如果左边和右边都有 说明这个节点就是最近的公共祖先 就返回

代码

#include"cheader.h"struct TreeNode{int val;struct TreeNode*left;struct TreeNode*right;};classSolution{public:intlowestCommonAncestor(TreeNode* root,int o1,int o2){if(root==nullptr)return-1;if(root->val== o1|| root->val== o2)return root->val;int left=lowestCommonAncestor(root->left, o1, o2);int right=lowestCommonAncestor(root->right, o1, o2);if(left==-1&& right==-1)return-1;elseif(left==-1)return right;elseif(right==-1)return left;elsereturn root->val;}};

今天也是爱zz的一天！