题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
后续遍历非递归解法：
1. 需要设置两个标志位find1和find2，代表是否找到这两个数.
2. 在后序遍历进栈的过程中，如果一个数字都没找到，就将结点p和标识1进站，找到其中一个后，对应标志位置true，在此之后将节点p和标志位0进栈。
3. 在后序遍历出栈的过程中，如果两个数都已经找到，并且标识为1，则这个节点就为最近公共父节点。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
stack<pair<TreeNode*, int>> s;
TreeNode *p = root, *pre = nullptr;
bool find1 = false, find2 = false;
int tmp;
while(p || !s.empty()) {
while(p) {
if(!find1 && !find2)
s.emplace(p, 1);
else
s.emplace(p, 0);
if(p->val == o1)
find1 = true;
else if(p->val == o2)
find2 = true;
p = p->left;
}
p = s.top().first;
tmp = s.top().second;
if(p->right && p->right != pre) {
p = p->right;
}
else {
if(tmp && find1 && find2)
return p->val;
if(p->val == o1)
find1 = true;
else if(p->val == o2)
find2 = true;
s.pop();
pre = p;
p = nullptr;
}
}
return -1;
}
};
查看11道真题和解析