Open youngyangyang04 opened 3 months ago
为啥我觉得是前序遍历呢,查找到母节点root == q or root == p就返回了啊,不是先处理的中间节点吗?
class Solution {
public TreeNode lowestCommonAncestor(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) return null; // 遍历到空节点并返回
if (node == p || node == q) return node; // 找到目标节点并返回
TreeNode left = lowestCommonAncestor(node.left, p, q); // 继续往左找
TreeNode right = lowestCommonAncestor(node.right, p, q); // 继续往右找
if (left != null && right != null) return node; // p、q 分别在子树, node 就是最近公共祖先
else if (left == null) return right; // p、q 都在右子树, right 就是最近公共祖先
else return left; // p、q 都在左子树, left 就是最近公共祖先
}
}
@Louthric
为啥我觉得是前序遍历呢,查找到母节点root == q or root == p就返回了啊,不是先处理的中间节点吗?
我觉得前序不对,比如示例1中:p在左子树、q在右子树。前序和中序都不是回溯过程,而后序是左右子树遍历结束之后,再来判断中节点。
@Louthric
为啥我觉得是前序遍历呢,查找到母节点root == q or root == p就返回了啊,不是先处理的中间节点吗?
我觉得前序不对,比如示例1中:p在左子树、q在右子树。前序和中序都不是回溯过程,而后序是左右子树遍历结束之后,再来判断中节点。
OK,有点理解了,谢谢
其实可以直接dfs存储查找p, q两节点的路径,然后同时遍历两个路径遇到不一样节点说明就不是公共节点了,最后一个一样的节点就是最近公共祖先,这样可以不用从下往上遍历而是从上往下遍历
对于第二种情况:节点本身p,它拥有一个子孙节点q;为什么包含在第一种情况的逻辑中呢?如果p是q的子孙节点,在遍历的时候匹配到p的时候,直接return了,并没有向下继续匹配啊?怎么能确定q在存在于子节点呢
分享我的解法 两个递归函数 第一个递归是后序遍历找祖先 第二个递归是判断这个node能不能当祖先
class Solution {
public:
bool traversal(TreeNode node, TreeNode p, TreeNode q, bool Ped, bool Qed) {
if (node == NULL) return false;
if (node == p) Ped = true;
if (node == q) Qed = true;
if (Ped && Qed) return true;
if (node->left) {
if (traversal(node->left, p, q, Ped, Qed)) return true;
}
if (node->right) {
if (traversal(node->right, p, q, Ped, Qed)) return true;
}
return false;
}
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == NULL) return NULL;
TreeNode node;
if (root->left) {
node = lowestCommonAncestor(root->left, p, q);
if (node) return node;
}
if (root->right) {
node = lowestCommonAncestor(root->right, p, q);
if (node) return node;
}
bool Ped = false, Qed = false;
if (traversal(root, p, q, &Ped, &Qed)) return root;
return NULL;
}
};
https://www.programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html