24, 두 갈래 트리 중 하나가 되는 경로

1657 단어
제목은 두 갈래 트리와 정수를 입력하고 두 갈래 트리의 결점 값과 정수를 입력하기 위한 모든 경로를 출력합니다.경로는 나무의 뿌리 결점에서 시작하여 잎 결점까지 내려가는 결점으로 경로를 형성합니다.
이 문제 참고 사항:
  • 귀속이 끝난 후 부모 노드로 돌아갑니다
  • ArrayList의 복제본
  • 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> lists = new ArrayList>();
            if(root==null){
                return lists;
            }
            ArrayList list = new ArrayList<>();
            FindPath(root,target,list,lists);
            return lists;
        }
        
        int curr = 0;
        
        public void FindPath(TreeNode root,int target, ArrayList list,ArrayList> lists) {
            if(root!=null){
                curr+=root.val;
                list.add(root.val);
            }
            // 
            if(root.left==null&&root.right==null){
                if(curr==target){
                    // new list 
                    ArrayList list2 = new ArrayList<>();
                    list2 = (ArrayList)list.clone();
                    lists.add(list2);
                }
            }
            
            if(root.left != null)
                FindPath(root.left,target,list,lists);
            if(root.right != null)
                FindPath(root.right,target,list,lists);
            
            // , 
            curr-=root.val;
            list.remove(list.size()-1); 
        }
    }
    

    좋은 웹페이지 즐겨찾기