leetcode - 437 - 경로 총화 III - java

제목 및 테스트

package pid437;


/* 437.      III

       ，               。

                。

           ，           ，            （          ）。

      1000   ，         [-1000000,1000000]    。

  ：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

   3。    8     :

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11



*/
public class main {
	
	public static void main(String[] args) {
		Object[] x=new Object[]{10,5,-3,3,2,null,11,3,-2,null,1,null,null,null,null};	
		BinaryTree tree=new BinaryTree(x);
		tree.printTree(tree.root);
		System.out.println("ito2="+8);
		test(tree.root,8);
		
		
	}
		 
	private static void test(TreeNode ito,int ito2) {
		Solution solution = new Solution();
		int rtn;		
		long begin = System.currentTimeMillis();
		rtn = solution.pathSum(ito,ito2);//    
		long end = System.currentTimeMillis();		
		System.out.println("rtn=" );
		System.out.println(rtn);
		System.out.println();
		System.out.println("  ：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

생각해 내지 못 하 다
해법 1 (남 의 것)
모든 노드 를 옮 겨 다 닌 다.관건: 귀속
현재 노드 를 경로 종점 으로 하 는 모든 경로 와관건: 루트 노드 에서 현재 노드 로 의 경 로 를 배열 로 저장 합 니 다.
현재 결산 점 을 최종 잎 결산 점 으로 위로 거 슬러 올 라 가 고 경로 의 모든 결산 점 은 뿌리 노드 에서 현재 결산 점 까지 의 경로 와 sum 의 경로 갯 수 입 니 다.그리고 같은 방법 으로 자신의 아이의 결점 을 최종 잎 결점 으로 계산한다.
바로 sum 대표 가 얻 고자 하 는 것 과 array 는 진짜 루트 에서 이 노드 까지 의 모든 노드 를 나타 낸다.이 노드 를 계산 하면 이 노드 + 상급 노드, 이 노드 + 상급 노드 +... + root, 즉 끊임없이 위로 sum 을 계산 하고 그 중에서 sum 의 개 수 를 계산 한 다음 에 하위 노드 로 돌아 갑 니 다.

public int pathSum(TreeNode root, int sum) {
        return pathSum(root, sum, new int[1000], 0);
    }

    public int pathSum(TreeNode root, int sum, int[] array/*    */, int p/*      */) {
        if (root == null) {
            return 0;
        }
        int tmp = root.val;
        int n = root.val == sum ? 1 : 0;
        for (int i = p - 1; i >= 0; i--) {
            tmp += array[i];
            if (tmp == sum) {
                n++;
            }
        }
        array[p] = root.val;
        int n1 = pathSum(root.left, sum, array, p + 1);
        int n2 = pathSum(root.right, sum, array, p + 1);
        return n + n1 + n2;
    }