java - 一段递归代码的问题

Question

在一篇博客上看到了一个递归函数，但我感觉划线的那一行似乎永远不为true呢？

因为函数里的第一个判断条件：

if (!root || p == root || q == root) return root;

就决定了left必定是p,q,null之一吧？

我对递归的理解不太深刻,不知道理解的对不对？谢谢。

Answer 1

우선, 이 재귀 함수에는 4가지 가능한 반환 값이 있다는 점을 이해해야 합니다.

1. null은 이 재귀가 리프 노드에 도달하여 계속할 수 없음을 의미합니다.

2. p는 이 재귀가 p 노드를 만났음을 나타냅니다.

3. q, 이 재귀가 q 노드를 만났음을 나타냅니다.

4. lowestCommonAncestor는 발견된 가장 낮은 공통 조상 노드를 나타냅니다.

이렇게 말하는 이유는
<1> if (!root || p == root || q == root) return root;
이기 때문에 처음 세 가지 가능성을 쉽게 이해해야 합니다. 이 코드 줄을 볼 수 있습니다.

다시 살펴보세요(축약하겠습니다)
<2> left = lowerCommonAncestor(left, p, q);
<3> right = lowerCommonAncestor(right, p, q);
이 두 줄입니다. 실제 가장 낮은CommonAncestor를 찾기 전에 이 함수는 null, q, p만 반환할 수 있습니다.
이 두 줄을 보고 다시 판단하세요
<4> if (left && left != p && left != q) return left;
<5> if (right && right != p && right != q) return right;
<2> 및 <3>의 반환 값이 null, p, q인 경우 이 두 가지 판단 조건을 충족할 수 없으므로 돌아왔다.
그래서 다음 판단으로 들어가야 합니다
<6> if (left && right) return root;
이 문장은 무엇을 의미하나요? <4>, <5>의 판단에서 반환이 없으면 왼쪽과 오른쪽은 null, p, q 중 하나만 가능하다는 뜻이고
여기서도 왼쪽과 오른쪽이 제한됩니다. null이 아니어야 합니다. 즉, 이때 왼쪽과 오른쪽 중 하나는 p이고 다른 하나는 q여야 합니다.
이때 이 수준의 재귀함수(이 수준의 재귀함수임을 참고하세요)의 루트가 가장 낮은CommonAncesstor이므로
반환됩니다.
마지막 문장
<7> return left ? left : right;
이제 여기까지 왔으니 왼쪽과 오른쪽 중 적어도 하나가 null이고 null이 아닌 것을 반환한다는 의미입니다. 또는 둘 다인 경우
모두 null인 경우 null을 반환합니다.

이제 <2> 및 <3>에서 lowerCommonAncesstor 재귀 함수의 호출을 살펴보세요. 현재
노드의 왼쪽과 오른쪽에서 p를 검색하는 것으로 생각할 수 있습니다. q를 사용하면 네 가지 종류의 결과가 나타납니다.

1. p와 q가 이 분기에 전혀 없음을 나타내는 null을 반환합니다.

2. p를 반환합니다. 이는 이 분기에 p만 있고 q가 없음을 나타냅니다.

3. q를 반환합니다. 이는 이 분기에 q만 있고 p는 없음을 나타냅니다.

4. 이 분기에 p와 q가 모두 있으므로 공통 조상을 찾았음을 나타내는 lowerCommonAncesstor를 반환합니다!

제가 말씀드린 내용이 충분하지 않을 수도 있으니 도움이 되셨으면 좋겠습니다 :)

Answer 2

첫 번째 조건은 루트를 결정하는 것이고, 두 번째 조건은 왼쪽을 결정하는 것입니다.