[LeetCode] 112. Path Sum

leetcode.com/problems/path-sum/

Path Sum - LeetCode

트리문제에 익숙해지고자 트리문제를 한번 더 풀어보기로 했다.

덕분에 문제 이해는 빨라졌지만, 코드 풀이는 아직 부족한 듯..힘내자!

 

첫 풀이

단말노드경로까지 더한 합계리스트를 담아두고 꺼냈을 때 targetSum이 되는 true를 반환하는 걸로 생각했는데, 그러려면 배열도 써야 하고, 값을 찾을 때 for문도 써야해서 타임도 오버 메모리도 오버된다.

getSum 메서드에서 순서도 정확하게 정비가 안됐다.

간단하게 로직을 정리해서 코드로 구현하는 게 정말 쉬운일이 아니구나

	public List<Integer> getSum(TreeNode root, int getSum) {
		List<Integer> sumList = new ArrayList<Integer>();
		if(root!=null) {
			getSum += root.val;
			while(root.left!=null || root.right!=null) {
				if(root.left!=null) {
					getSum(root.left, getSum);
				}
				if(root.right!=null) {
					getSum(root.right, getSum);
				}
				sumList.add(getSum);
			}
		}
		return sumList;
	}

	//루트부터 단말 노드부터 더한 값이 target이 되는 경로가 있으면 true
    public boolean hasPathSum(TreeNode root, int targetSum) {
    	boolean hasPath = false;
    	List<Integer> sumList = getSum(root, 0);
    	for(int target :sumList){
    		if(target==targetSum) {
    			hasPath = true;
    		}
    	}
    	return hasPath;
    }

 

아주 깔끔한 해답코드
이렇게 해결되는 거였다니 코테를 풀때마다 매번 답안코드에 경이로움을 느낀다.
targetSum 에서 빼기를 할 생각을 못했다.

당연히 root에서부터 더한다고 생각했는데 발상의 전환을 하는 연습을 해야 할 듯

	public boolean hasPathSum(TreeNode root, int targetSum) {
		if(root == null)  return false; 
		
		if(root.left==null && root.right==null && targetSum-root.val==0) {
			return true;
		}else {
			return hasPathSum(root.left, targetSum-root.val) || hasPathSum(root.right, targetSum-root.val);
		}
	}

 

자바에서 메서드 안에 메서드를 만들 수 있을까 ? 
www.geeksforgeeks.org/method-within-method-in-java/

Method within method in java - GeeksforGeeks

재귀함수에서 스택 사용 이해 도움
StackDiagrams.html

medium.com/@mirandarevans/recursion-diagram-18209cf4be50

www.youtube.com/watch?v=ygK0YON10sQ