1 | Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. |
常规面试题,求最低公共祖先
这里我们用路径交集的方法
首先求出根节点到两个节点的路径,放进stack里面(之前放在了vector里面,其实也ok),然后不断pop两个stack,直到它们顶部不同,那么上一个出栈的节点就是公共祖先
1 | /** |
递归写法1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || p == root || q == root) return root;
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
return !l ? r : !r ? l : root;
}
};