검지offer 면접문제 25-이차수 중 어느 값의 경로

1518 단어
제목:
두 갈래 트리와 정수를 입력하고 두 갈래 트리의 노드 값과 정수를 입력하기 위한 모든 경로를 출력합니다.
나무의 뿌리 노드에서 시작하여 잎 노드가 지나가는 노드까지 내려가서 하나의 경로를 형성한다.
사실은 나무가 두루 다니는 것이다.
두루 돌아다니면서 궤적을 기록하다.
인쇄할 때 궤적을 봐야 합니다: 처음부터 끝까지
아래로 내려갈 때 궤적의 끝에 추가해야 한다.
위로 반올림할 때 궤적의 끝으로 줄여야 한다.
그래서 여기서는 Linked List를 사용합니다.
트리의 정의는 다음과 같습니다.
package com.aii.algorithm;

public class TreeNode {
	int value;
	TreeNode left;
	TreeNode right;

	@Override
	public String toString() {
		return "TreeNode [value=" + value + "]";
	}

	public TreeNode(int value) {
		super();
		this.value = value;
	}

}

구현 코드:
package com.aii.algorithm;

import java.util.LinkedList;

public class FindPath {

	public void find(TreeNode root, int target, LinkedList<TreeNode> list) {
		if (root == null) {
			return;
		}
		if (list == null) {
			list = new LinkedList<TreeNode>();
		}

		//  
		int currentValue = root.value;
		//  
		target = target - currentValue;
		//  -
		if (root.left == null && root.right == null) {
			//  , 
			if (target == 0) {
				print(list, root);
				return;
			}
			//  , 
			return;
		}
		//  ,, 
		list.offer(root);
		//  
		find(root.left, target, list);
		find(root.right, target, list);
		//  , ,
		list.removeLast();
	}

	private void print(LinkedList<TreeNode> list, TreeNode root) {
		for (TreeNode tr : list) {
			System.out.print(tr);
			System.out.print(",");
		}
		System.out.println(root);
	}
}

좋은 웹페이지 즐겨찾기