검지offer-24: 두 갈래 나무 중 어느 값의 경로

7407 단어 검지offer

제목 설명


두 갈래 나무의 루트 노드와 정수를 입력하고 두 갈래 나무의 결점 값과 정수를 입력하는 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.(주의: 값을 되돌려주는list에서 그룹 길이가 큰 그룹이 앞에 있습니다)

생각


dfs 알고리즘

코드

public class Solution24 {
     


    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
     

        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> trace = new ArrayList<>();
        if (root == null)
            return ret;

        pa(root, target, ret, trace);
        return ret;
    }

    public void pa(TreeNode root, int target, ArrayList<ArrayList<Integer>> ret, ArrayList<Integer> trace) {
     


        trace.add(root.val);
        // 。
        if (root.left == null && root.right == null) {
     
            if (target == root.val)
                ret.add(new ArrayList<>(trace));
        }
        if (root.left != null)
            pa(root.left, target - root.val, ret, trace);
        if (root.right != null)
            pa(root.right, target - root.val, ret, trace);

        // , , 
        trace.remove(trace.size() - 1);

    }


    public static void main(String[] args) {
     



    }


}

좋은 웹페이지 즐겨찾기