Leetcode 113 Path Sum II는 두 갈래 나무와 하나의 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾아서 목표와 같은 경로를 찾아낸다

1575 단어 leetcode
제목:
두 갈래 나무와 목표와 뿌리 노드에서 잎 노드까지의 모든 경로를 찾는 것은 목표와 같은 경로입니다.
설명: 잎 노드는 하위 노드가 없는 노드를 가리킨다.
예: 다음과 같은 두 갈래 트리와 목표 및sum = 22 ,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

반환:
[
   [5,4,11,2],
   [5,8,4,5]
]

해결 방법:
package test;

import java.util.ArrayList;
import java.util.List;

public class LC133Try1
{
	public List> pathSum(TreeNode root, int sum)
	{
		List> list = new ArrayList>();
		if(root==null){
			return list;
		}
		List temp= new ArrayList();
		getPass(root,sum,list,temp,0);
		return list;

	}
	public void getPass(TreeNode root,int sum,List> list, List temp,int add){
		/* 
		 * if(add>sum){
			return;
		}*/
		if(root.left==null && root.right==null){
			if(add+root.val==sum){
				temp.add(root.val);
				list.add(new ArrayList(temp));	
				temp.remove(temp.size()-1);
				
			}
			return;
		}else{
			if(root.left!=null){
				temp.add(root.val);
				getPass(root.left,sum,list,temp,add+root.val);
				temp.remove(temp.size()-1);
			}
			if(root.right!=null){
				temp.add(root.val);
				getPass(root.right,sum,list,temp,add+root.val);
				temp.remove(temp.size()-1);
			}
		}
	}
	
}

하하하

좋은 웹페이지 즐겨찾기