두 갈래 나 무 를 지정 합 니 다. 두 갈래 나 무 는 각 노드 의 값 이 유일 합 니 다. 뿌리 노드 부터 경로 에 있 는 모든 노드 의 노드 값 과 규정된 값 과 같은 경 로 를 찾 습 니 다.

1690 단어
사고방식: 먼저 (뿌리 노드 - 왼쪽 트 리 - 오른쪽 트 리) 를 옮 겨 다 니 는 방식 으로 이 진 트 리 의 모든 노드 를 방문 하고 뿌리 노드 가 이 노드 에 옮 겨 다 니 는 모든 노드 값 의 합 을 기록 하 며, 동시에 하나의 list 로 옮 겨 다 니 는 경 로 를 저장 합 니 다. 만약 에 노드 와 같은 값 이 주어진 값 이면 경 로 를 되 돌려 주 고, 잎 노드 가 끝 날 때 까지 돌아 갑 니 다.
사용 하 는 데이터 구조: Array List, stack
코드 는 다음 과 같 습 니 다:
import java.util.ArrayList;
import java.util.Stack;
/**
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;
        }
        Stack stack = new Stack<>();
        FindPath(root, target, stack, result);
        return result;
    }
    
    private void FindPath(TreeNode root, int target, Stack stack, ArrayList> result) {
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            if(root.val==target){
                ArrayList list = new ArrayList<>();
                for(int i:stack){
                    list.add(i);
                }
                list.add(root.val);
                result.add(list);
            }
        }else{
            stack.push(root.val);
            FindPath(root.left, target-root.val, stack, result);
            FindPath(root.right, target-root.val, stack, result);
            stack.pop();
        }
    }
}

좋은 웹페이지 즐겨찾기