中等 近期公共祖先
查看执行结果
34%通过给定一棵二叉树，找到两个节点的近期公共父节点(LCA)。
近期公共祖先是两个节点的公共的祖先节点且具有最大深度。
您在真实的面试中是否遇到过这个题？
Yes例子对于以下这棵二叉树
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
bool postOrder(TreeNode *root, TreeNode *A) {
if (root == nullptr)
return false;
if (root == A) {
return true;
}
return (postOrder(root->left,A)|| postOrder(root->right,A));
}
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// write your code here
if (root == nullptr )
return nullptr;
bool ra = postOrder(root->right,A);
bool rb = postOrder(root->right,B);
bool la = postOrder(root->left,A);
bool lb = postOrder(root->left,B);
if (ra && rb) {
return lowestCommonAncestor (root->right,A,B);
} else if (la && lb) {
return lowestCommonAncestor(root->left,A,B);
} else {
return root;
}
}
};
中等 近期公共祖先
查看执行结果
34%
通过
给定一棵二叉树，找到两个节点的近期公共父节点(LCA)。
近期公共祖先是两个节点的公共的祖先节点且具有最大深度。
您在真实的面试中是否遇到过这个题？
Yes
例子
对于以下这棵二叉树
4
/ \
3 7
/ \
5 6
LCA(3, 5) = 4
LCA(5, 6) = 7
LCA(6, 7) = 7
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
bool postOrder(TreeNode *root, TreeNode *A) {
if (root == nullptr)
return false;
if (root == A) {
return true;
}
return (postOrder(root->left,A)|| postOrder(root->right,A));
}
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// write your code here
if (root == nullptr )
return nullptr;
bool ra = postOrder(root->right,A);
bool rb = postOrder(root->right,B);
bool la = postOrder(root->left,A);
bool lb = postOrder(root->left,B);
if (ra && rb) {
return lowestCommonAncestor (root->right,A,B);
} else if (la && lb) {
return lowestCommonAncestor(root->left,A,B);
} else {
return root;
}
} };