[검지 offer] 두 갈래 나무와 어떤 값의 경로

1397 단어

제목 설명


두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.

문제 풀이 사고방식


앞뒤로 훑어보는 방식으로 어떤 결점에 접근할 때, 이 결점을 경로에 추가하고, 목표 값으로 이 노드의 값을 줄인다.만약 이 결점이 잎결점이고 목표 값이 이 노드의 값을 빼면 마침 0이 됩니다. 현재 경로가 요구에 부합되므로res수조에 넣겠습니다.현재 결점이 잎 결점이 아닌 경우 하위 결점에 계속 액세스합니다.현재 결점 접근이 끝나면 귀속 함수는 자동으로 부모 결점으로 돌아갑니다.따라서 함수가 종료되기 전에 경로에서 현재 결점을 삭제하여 부모 결점으로 돌아갈 때 경로가 루트 결점에서 부모 결점까지의 경로가 맞는지 확인합니다.

참조 코드

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    ArrayList > res = new ArrayList >();
    ArrayList temp = new ArrayList();
    public ArrayList> FindPath(TreeNode root,int target) {
        if(root == null)
            return res;
        target -= root.val;
        temp.add(root.val);
        if(target == 0 && root.left == null && root.right == null)
            res.add(new ArrayList(temp));
        else{
            FindPath(root.left, target);
            FindPath(root.right, target);
        }
        temp.remove(temp.size()-1);
        return res;
    }        
}
LeetCode OJ-129.Sum Root to Leaf Numbers
웹샵 제품 관리를 위한 CRUD 만들기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage