주어진 합계를 가진 이진 트리의 경로 수

Question

문제를 해결합니다. https://leetcode.com/problems/path-sum-iii/ 여기에 간략하게 언급 할 것입니다 : 총합 = 합계 인 이진 트리에서 경로 수를 찾습니다. 경로는 반드시 루트 (리프)에서 시작 (끝)하지 않아도됩니다. 경로가 아래로가는 한 유효한 경로로 간주되어야합니다. 여기

내 솔루션입니다 :

/** 
* Definition for a binary tree node. 
* public class TreeNode { 
*  int val; 
*  TreeNode left; 
*  TreeNode right; 
*  TreeNode(int x) { val = x; } 
* } 
*/ 

public class Solution { 
    public int pathSum(TreeNode root, int sum) { 
     int path = 0; 
     if(root.val == sum) 
      return 1; 
     else if(root.left == null && root.right == null) 
      return 0; 
     if(root.left != null){ 
      path += pathSum(root.left, sum - root.val); 
      path += pathSum(root.left, sum); 
     } 
     if(root.right != null){ 
      path += pathSum(root.right, sum - root.val); 
      path += pathSum(root.right, sum); 
     } 
     return path; 
    } 
} 

자신의 시스템에 따라 답은 3이지만, 나는 다음과 같은 입력을 4로 답을 얻고있다 :

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

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

Return 3. The paths that sum to 8 are: 

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

나는 시간을 보냈다 노력했다 내 코드가 제대로 작동하지 않는 이유를 설명하기 위해 문제를 파악할 수는 없습니다. 순진한 질문에 대한 죄송합니다

:(하지만이 나를 죽이고

Answer 1

이 제약 조건을 만족하지 못할 코드 :!이 나무와 의

these nodes should be continuous. 

예를 들어 루트 (값 10) 이 나무의 잎 (가치 -2), 그 합계는 8이다. 그러나 그것은 연속적으로 만족하지 않는다, 그래서 그것을 세지 않는다

아쉽게도 코드가이 사건을 걸러 낼 수 없습니다.

대안 솔루션 :

public class Solution { 
public int pathSum(TreeNode root, int sum) { 
    int path = traverse(root,sum); 
    return path; 
} 

public int traverse(TreeNode root, int sum){ 
    int path = 0; 
    if(root==null){ 
     return 0; 
    } 
    else{ 
     path += calcu(root,sum); 
     path += traverse(root.left,sum); 
     path += traverse(root.right,sum); 
     return path; 
    } 
} 

private int calcu(TreeNode root, int sum) { 
    if(root==null){ 
     return 0; 
    } 
    else if(root.val==sum){ 
     return 1 + calcu(root.left,sum-root.val)+calcu(root.right,sum-root.val); 
    } 
    else{ 
     return calcu(root.left,sum-root.val)+calcu(root.right,sum-root.val); 
    } 
} 
} 

설명 : traverse이 나무와, 루트 노드로 모든 TREENODE을 연속 전제 아래 대상 경로를 찾을 수 있습니다.

Answer 2

당신의 솔루션에 무엇이 잘못된 것인지 잘 모르겠습니다 만, 그것이 정확하다고 생각하지 않습니다. 우선, 루트가 8이면 즉시 반환하고 솔루션으로 루트 만 계산합니다. 이것은 내가 어떻게 할 것입니다 :

import java.util.ArrayList; 

public class Solution { 
    public static int pathSum(TreeNode root, int sum) { 
     return pathSum(root, sum, 0, new ArrayList<Integer>()); 
    } 

    public static int pathSum(TreeNode root, int sum, int count, ArrayList<Integer> arr) { 
     arr.add(root.val); 
     int acc = 0; 
     for (int i=arr.size()-1; i>=0; i--) { 
      acc += arr.get(i); 
      if (acc == sum) 
      count++; 
     } 
     if(root.left != null) 
      count = pathSum(root.left, sum, count, arr); 
     if(root.right != null) 
      count = pathSum(root.right, sum, count, arr); 
     arr.remove(arr.size()-1); 
     return count; 
    } 

    static class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 
    public TreeNode(int v) { 
     this.val = v; 
    } 
    } 

    public static void main(String[] args) { 
    TreeNode root = new TreeNode(10); 
    root.left = new TreeNode(5); 
    root.right = new TreeNode(-3); 
    root.left.left = new TreeNode(3); 
    root.left.right = new TreeNode(2); 
    root.right.right = new TreeNode(11); 
    root.left.left.left = new TreeNode(3); 
    root.left.left.right = new TreeNode(-2); 
    root.left.right.right = new TreeNode(1); 
    System.out.println(pathSum(root, 8)); 
    } 
} 

아이디어는 당신이 반복적으로 트리를 탐색으로 경로를 따라 값을 갖는 aarray을 채우는 당신이 돌아대로 요소를 제거 확인하고. 노드를 방문하면 해당 노드에서 루트에있는 모든 노드까지의 모든 합계를 고려해야합니다. 이들 중 누구라도 참조 값을 합칠 수 있습니다. 이 구현은 O 노드 (nlogn)입니다. n 노드를 탐색 할 때마다 각각에 대해 len의 배열을 통과하여 log (n)을 탐색합니다.

Answer 3

솔루션의 문제점은 10-2 = 8입니다. 여기서 10은 맨 위 루트 노드이고 -2은 하단 리프입니다. 그 사이의 모든 경로를 무시합니다.

나는 그것을 tamperedSum 부울로 해결할 수있었습니다. 우리는이 경우 8 원래 합 (노드)의 값을 공제 한 경우

public static int pathSum(TreeNode root, int sum, boolean tamperedSum) 
{ 
    int path = 0; 
    if(root.val == sum) 
     path = 1; 

    if(root.left == null && root.right == null) 
     return path; 

    if(root.left != null){ 
     path += pathSum(root.left, sum - root.val, true); 
     if (!tamperedSum) 
      path += pathSum(root.left, sum, false); 
    } 
    if(root.right != null){ 
     path += pathSum(root.right, sum - root.val, true); 
     if (!tamperedSum) 
      path += pathSum(root.right, sum, false); 
    } 
    return path; 
} 

tamperedSum 부울 true로 설정된다.

우리로 호출 할 것이다 :

pathSum(root, sum, false) 

아이디어는 합이 된 경우 경로의 노드 값이 이미 공제 된 즉, 우리는 더 이상으로 통과 할 수 있습니다 가 변조 없다는 것입니다 - 노드 아래의 지점에 있습니다.

그래서 노드 값을 sum - root.value에서 차감 할 때마다 tamperedSum을 true으로 설정합니다. 그 후, 그 아래의 모든 노드는 그 노드 값을 빼지 않고 sum을 통과 할 수 없습니다.

Answer 4

새로운 내부 경로에있는 경우 초기 합계에서 시작하지 않는 것이 솔루션의 문제점입니다.

내부 경로를 이동할 때 포함 된 합계와 원본 합계를 추적해야합니다.

수정 된 알고리즘 사본을 아래에서 찾으십시오.

public static class TreeNode { 
    int val; 
    TreeNode left; 
    TreeNode right; 

    boolean visitedAsRoot = false; 

    TreeNode(int x) { 
     val = x; 
    } 
} 

public static int pathSum(TreeNode root, int accomulate, int sum) { 
    int path = 0; 
    if (root.val == accomulate) 
     return 1; 
    else if (root.left == null && root.right == null) 
     return 0; 
    if (root.left != null) { 
     path += pathSum(root.left, accomulate - root.val, sum); 
     if (!root.left.visitedAsRoot) { 
      root.left.visitedAsRoot = true; 
      path += pathSum(root.left, sum, sum); 
     } 
    } 
    if (root.right != null) { 
     path += pathSum(root.right, accomulate - root.val, sum); 
     if (!root.right.visitedAsRoot) { 
      root.right.visitedAsRoot = true; 
      path += pathSum(root.right, sum, sum); 
     } 
    } 
    return path; 
} 

public static void main(String args[]) { 
    TreeNode t1 = new TreeNode(3); 
    TreeNode t2 = new TreeNode(-2); 
    TreeNode t3 = new TreeNode(1); 
    TreeNode t4 = new TreeNode(3); 
    TreeNode t5 = new TreeNode(2); 
    TreeNode t6 = new TreeNode(11); 
    TreeNode t7 = new TreeNode(5); 
    TreeNode t8 = new TreeNode(-3); 
    TreeNode t9 = new TreeNode(10); 

    t4.left = t1; 
    t4.right = t2; 

    t5.right = t3; 

    t7.left = t4; 
    t7.right = t5; 

    t8.right = t6; 

    t9.left = t7; 
    t9.right = t8; 

    System.out.println(pathSum(t9, 8, 8)); 
}