면접 문제두 갈래 트리와 어떤 값의 경로 dfs
1795 단어 차례로 돌아가다
제목 설명
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다.나무의 뿌리 노드에서 시작하여 잎 노드가 지나가는 노드까지 내려가서 하나의 경로를 형성한다.예: 다음과 같은 두 갈래 트리와 목표와sum=22, 5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
반환: [[[5,4,11,2], [5,8,4,5] 팁: 노드 총수<= 10000 출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.
dfs 해법
생각
dfs 방법을 채택하여 먼저 반복한다.나무의 잎 노드를 훑어보고 뿌리 노드에서 잎 노드까지의 경로와 만약sum값을 정하는 것과 같으면path집합을 추가합니다.
여기에서 두 필드LinkedList> paths
와 LinkedList path 를 정의합니다. 전자는 검색된 조건을 충족시키는 경로를 기록하고 후자는 현재 경로를 유지하는 데 사용됩니다.
원시적인 dps가 두루 다니고 검색 순서는 두 갈래 나무의 인접 노드에 따라 이동하지 않습니다.그러므로 검색 순서가 반드시 연속적인 경로는 아니다.여기에 하나의 처리를 채택하여 연속적인 경로를 유지하는 것을 실현하였다.추이 과정에서 현재 노드를 유지보수의 경로 체인 테이블에 추가하고 마지막으로 왼쪽, 오른쪽 트리에 각각 방문한 후 현재 노드를 유지보수의 경로 목록에서 꺼냅니다.
java 코드
private LinkedList> paths = new LinkedList<>();
private LinkedList path = new LinkedList<>();
public List> pathSum(TreeNode root, int sum) {
dfs(root, sum);
return paths;
}
public void dfs(TreeNode aRoot, int aSum){
if(aRoot==null)
return;
int val = aRoot.val;
path.add(val);
if(aSum-val == 0 && aRoot.left==null && aRoot.right==null){
paths.add(new LinkedList(path));
}
dfs(aRoot.left, aSum-val);
dfs(aRoot.right, aSum-val);
path.removeLast();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 백엔드에서 데이터를 트리로 변환하고 맵은 json 트리를 생성하여 백엔드로 되돌려줍니다. (백엔드 변환)
java 백엔드, 데이터를 트리로 변환하고,map는 json 트리를 생성하여 전방으로 되돌려줍니다(백엔드 변환)
1. 왜 이런 블로그를 쓰나요?
2.java 백엔드 코드
3. 전환된 데이터는 다음과 유사한 형식으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
생각
dfs 방법을 채택하여 먼저 반복한다.나무의 잎 노드를 훑어보고 뿌리 노드에서 잎 노드까지의 경로와 만약sum값을 정하는 것과 같으면path집합을 추가합니다.
여기에서 두 필드
LinkedList> paths
와 LinkedList path 를 정의합니다. 전자는 검색된 조건을 충족시키는 경로를 기록하고 후자는 현재 경로를 유지하는 데 사용됩니다.원시적인 dps가 두루 다니고 검색 순서는 두 갈래 나무의 인접 노드에 따라 이동하지 않습니다.그러므로 검색 순서가 반드시 연속적인 경로는 아니다.여기에 하나의 처리를 채택하여 연속적인 경로를 유지하는 것을 실현하였다.추이 과정에서 현재 노드를 유지보수의 경로 체인 테이블에 추가하고 마지막으로 왼쪽, 오른쪽 트리에 각각 방문한 후 현재 노드를 유지보수의 경로 목록에서 꺼냅니다.
java 코드
private LinkedList> paths = new LinkedList<>();
private LinkedList path = new LinkedList<>();
public List> pathSum(TreeNode root, int sum) {
dfs(root, sum);
return paths;
}
public void dfs(TreeNode aRoot, int aSum){
if(aRoot==null)
return;
int val = aRoot.val;
path.add(val);
if(aSum-val == 0 && aRoot.left==null && aRoot.right==null){
paths.add(new LinkedList(path));
}
dfs(aRoot.left, aSum-val);
dfs(aRoot.right, aSum-val);
path.removeLast();
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
java 백엔드에서 데이터를 트리로 변환하고 맵은 json 트리를 생성하여 백엔드로 되돌려줍니다. (백엔드 변환)java 백엔드, 데이터를 트리로 변환하고,map는 json 트리를 생성하여 전방으로 되돌려줍니다(백엔드 변환) 1. 왜 이런 블로그를 쓰나요? 2.java 백엔드 코드 3. 전환된 데이터는 다음과 유사한 형식으로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
