검지 Offer Java 섹션 문제 34: 두 갈래 트리 중 한 값의 경로

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

연습 주소


https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca

답안을 참고하다

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 {
    public ArrayList> FindPath(TreeNode root, int target) {
        ArrayList> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        find(root, target, 0, new ArrayList(), result);
        return result;
    }
    
    private void find(TreeNode node, int target, int sum, ArrayList path, ArrayList> result) {
        sum += node.val;
        path.add(node.val);
        //  ， ， 
        if (node.left == null && node.right == null) {
            if (sum == target) {
                ArrayList list = new ArrayList<>();
                for (Integer val : path) {
                    list.add(val);
                }
                result.add(list);
            }
        } else {
            //  ， 
            if (node.left != null) {
                find(node.left, target, sum, path, result);
            }
            if (node.right != null) {
                find(node.right, target, sum, path, result);
            }
        }
        //  ， 
        path.remove(path.size() - 1);
    }
}

복잡도 분석

  • 시간 복잡도: O(n)..
  • 공간 복잡도: O(logn)..

    • 검지 Offer Java 버전 디렉토리 검지 Offer Java 버전 테마
    u699The Falling Leaves
    [LeetCode] 112. Path Sum

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

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