두 갈래 트리 중 하나가 되는 값
4294 단어 데이터 구조와 알고리즘
제목
제목: 두 갈래 나무와 정수를 입력하고 두 갈래 나무의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 루트 노드에서 시작하여 잎 노드가 지나가는 노드까지 내려가서 하나의 경로를 형성한다.
주의: 경로는 루트 노드에서 시작해서 잎 노드까지 가야 합니다...처음에는 줄곧 이 점을 알아차리지 못했다.
생각
두 갈래 트리의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다. 잎 노드에 접근할 때 우리는 앞에 어떤 노드가 지나갔는지 알 수 없기 때문에 지나간 노드를 저장하기 위해 집합이 필요합니다. (이 집합은 반드시 선진적인 후출이어야 합니다.)
경로는 반드시 루트 노드에서 시작하여 잎 노드까지 옮겨야 한다. 따라서 우리는 앞의 순서에 따라 루트 노드에서 특정한 잎 노드까지 옮겨다닌 다음에 그 노드와 요구하는 노드가 같은지 아닌지를 판단하고 같으면 이 경로의 모든 노드 값을 출력한다.
만약 같지 않거나 인쇄가 끝난 후에 집합에서 이 노드를 삭제하고 부모 노드로 돌아가 계속 판단하기
java 코드
package com.ca;
import java.util.ArrayDeque;
//
class Node{
int value;
Node leftTree;
Node rightTree;
public Node(int value){
this.value = value;
}
@Override
public String toString(){
return this.value + "";
}
}
public class SumFixedValue {
public static void main(String[] args) {
Node root = new Node(8);
root.leftTree = new Node(2);
root.leftTree.leftTree = new Node(5);
root.leftTree.rightTree = new Node(9);
root.rightTree = new Node(3);
root.rightTree.rightTree = new Node(4);
int sum = 15;
int CurrentSum = 0;
ArrayDeque ad = new ArrayDeque();
Search(root,ad,sum,CurrentSum);
}
public static void Search(Node root,ArrayDeque ad,int sum,int currentSum){
if(root == null){
return;
}
currentSum += root.value;
ad.push(root);
// , , sum ,
boolean is = (root.leftTree == null) && (root.rightTree == null);
if(currentSum == sum && is){
System.out.println(ad);
}
// ,
if(root.leftTree != null){
Search(root.leftTree,ad,sum,currentSum);
}
if(root.rightTree != null){
Search(root.rightTree,ad,sum,currentSum);
}
// ,
ad.pop();
}
}
확장
만약에 제목에 한정된 경로가 없으면 루트 노드에서 시작해서 잎 노드가 끝날 때까지 해야 합니다. 어디서부터 어디까지 끝나든지 이 경로의 노드와 요구값만 있으면 어떻게 해야 합니까?생각지도 못했어...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.