[알고리즘 학습] 트 리 인쇄 경로
해법 과 분석: 1. 나무의 뿌리 결점 에서 잎 결점 까지 옮 겨 다 녀 야 하 는데 그 중에서 결점 을 거 친 값 을 누적 해 야 한다.2. 잎 결산 점 에 누적 되 었 을 때 결산 점 값 과 sum 의 값 을 누적 하고 같 으 면 경 로 를 출력 합 니 다.만약 같 지 않다 면, 윗 층 으로 돌아 가 다른 잎의 결점 을 찾 아 라.3. 노드 경 로 를 저장 하고 이전 노드 로 돌아 갈 수 있 으 며 스 택 으로 노드 를 저장 할 수 있 습 니 다.4. 재 귀적 으로 이 해법 을 설명 할 수 있다.
참조 코드 는 다음 과 같 습 니 다.
/** * */
static class TreeNode
{
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val)
{
this.val = val;
}
public TreeNode(int val, TreeNode left, TreeNode right)
{
this.val = val;
this.left = left;
this.right = right;
}
}
/** * */
public static void findPath(TreeNode root, int sum)
{
if (root == null) return;
Stack<Integer> paths = new Stack<Integer>();
findPath(root, paths, sum, 0);
}
/** * */
private static void findPath(TreeNode root, Stack<Integer> paths, int sum,int currentSum)
{
currentSum += root.val;
boolean isLeaf = root.left == null && root.right == null;
paths.push(root.val);
if (isLeaf && currentSum == sum)
{
printPath(paths);
}
if (root.left != null)
{
findPath(root.left, paths, sum, currentSum);
}
if (root.right != null)
{
findPath(root.right, paths, sum, currentSum);
}
paths.pop();
}
/** * */
static void printPath(Stack<Integer> paths)
{
if (paths.isEmpty()) return;
for (Integer item : paths)
{
System.out.print(item + " - ");
}
System.out.println();
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
