면접 문제(34) 두 갈래 나무와 어떤 값의 경로
2063 단어 검지offer
사고방식: 먼저 주의해야 한다. 반드시 뿌리 노드에서 잎 노드로 가는 경로가 효과적인 경로이고 뿌리 노드에서 내부 노드로 가는 경로가 무효이다.두 갈래 나무의 귀속의 구조적 특성 때문에 귀속으로 문제를 풀 수 있다. 1) 먼저 입력 정수와 현재 노드의 값이 같은지 판단하고, 만약 동일하고 이 노드가 잎 노드라면 현재 경로를 문제에 부합되는 경로 집합에 넣은 다음에 귀속으로 좌우 나무를 검사하고, 다른 경우에는 직접 좌우 나무를 귀속 검사한다.2) 한 층의 귀속이 종료되기 전에 이 층의 귀속이 들어간 노드를 삭제해야 다른 귀속 호출 시 경로의 노드 값을 방해하지 않습니다.
코드 구현 (소객망 AC에서):
import java.util.ArrayList;
private ArrayList> paths = new ArrayList>();
private ArrayList path = new ArrayList<>();
public ArrayList> FindPath(TreeNode root,int target) {
//
if(root == null)
return paths;
// path
path.add(root.val);
target -= root.val;
// path
if(target == 0 && root.left == null && root.right == null)
{
// ： ArrayList ， path paths
paths.add(new ArrayList(path));
}
FindPath(root.left, target);
FindPath(root.right, target);
// ！
path.remove(path.size()-1);
return paths;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
20200326 - 검지offer 면접문제 27: 두 갈래 나무의 거울이솔 위 안에 28문제의 답안이 있는데 어떻게 꼬치는지 모르겠다.간단해....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
