두 갈래 트리 중 하나가 되는 값

제목


제목: 두 갈래 나무와 정수를 입력하고 두 갈래 나무의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 루트 노드에서 시작하여 잎 노드가 지나가는 노드까지 내려가서 하나의 경로를 형성한다.
주의: 경로는 루트 노드에서 시작해서 잎 노드까지 가야 합니다...처음에는 줄곧 이 점을 알아차리지 못했다.

생각


두 갈래 트리의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다. 잎 노드에 접근할 때 우리는 앞에 어떤 노드가 지나갔는지 알 수 없기 때문에 지나간 노드를 저장하기 위해 집합이 필요합니다. (이 집합은 반드시 선진적인 후출이어야 합니다.)
경로는 반드시 루트 노드에서 시작하여 잎 노드까지 옮겨야 한다. 따라서 우리는 앞의 순서에 따라 루트 노드에서 특정한 잎 노드까지 옮겨다닌 다음에 그 노드와 요구하는 노드가 같은지 아닌지를 판단하고 같으면 이 경로의 모든 노드 값을 출력한다.
만약 같지 않거나 인쇄가 끝난 후에 집합에서 이 노드를 삭제하고 부모 노드로 돌아가 계속 판단하기

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();

    }
}

확장


만약에 제목에 한정된 경로가 없으면 루트 노드에서 시작해서 잎 노드가 끝날 때까지 해야 합니다. 어디서부터 어디까지 끝나든지 이 경로의 노드와 요구값만 있으면 어떻게 해야 합니까?생각지도 못했어...

좋은 웹페이지 즐겨찾기