이진 트리에서 경로 합계를 계산하십시오.

이진 트리의 루트에서 리프까지의 경로 합계를 계산하려고합니다. 작동하지 않는 것 같아, doesIt의 값은 true가되지만 재귀이기 때문에 스택이 팝되면 다시 false로 전환됩니다. 그것을 고치는 법을 모릅니다. 코드를 변경하여 doIt 값이 true로 변경되면 스택까지 모든 것을 전달하도록 코드를 변경하려면 어떻게해야합니까? [5,4,8,11, NULL, NULL, NULL, 7,2] 중위 그래서 5 두 아이 4와 8이이진 트리에서 경로 합계를 계산하십시오.

, 4 일 아이 (11), 8이 있습니다

나무가 고려 아이

hasPathSum (루트, 22)

public boolean hasPathSum(TreeNode root, int sum) { 
    boolean doesIt = false; 
    if (root != null) 
    { 
     doesIt = pathSum(root, sum, 0, doesIt); 
    } 
    return doesIt; 
} 

private static boolean pathSum(TreeNode root, int sum, int sumSoFar, boolean doesIt) 
{ 
    if (root.left == null && root.right == null) 
    { 
     if (sumSoFar+root.val == sum) 
     { 
      doesIt = true; 
      return doesIt; 
     } 
     return doesIt; 
    } 

    if (root.left != null) 
    { 
     pathSum(root.left, sum, sumSoFar+root.val,doesIt); 
    } 

    if (root.right != null) 
    { 
     pathSum(root.right, sum, sumSoFar+root.val,doesIt); 
    } 

    return doesIt; 
}

출처

2017-03-27 khizarshad

약 7과 2는 어떨까요? 나무를 그리고 대답을 업데이트하십시오. – Vaibs

'pathSum'가 스스로를 재귀 적으로 호출 할 때 내부 'pathSum' 호출은 값을 반환하지만 사용하지는 않습니다. 이러한 반환 값을 사용하도록 메서드를 수정하면됩니다. 나는 방법이 무엇을 해야하는지 이해하지 못하기 때문에 어떻게, 모르겠다. – ajb

당신은 단지 어린이 메서드를 호출하여 주어진 값을 던지는이 없습니다. 나는 약간이 당신의 코드를 다시 작성 :

private static boolean pathSum(TreeNode root, final int sum, int sumSoFar) { 
    if (root == null) return false; 
    if (root.left == null && root.right == null) return sumSoFar + root.val == sum; 
    return pathSum(root.left, sum, sumSoFar + root.val) || pathSum(root.right, sum, sumSoFar + root.val); 
}

그것의 기본 재귀 : null 노드 대답은 정의에 의해 거짓을 위해, 잎은 두 가지 중 하나에서 성공을 달성하기 위해 노력하고 또 다른 코너의 경우, 일반적인 경우입니다.

P. 질문과 메소드 서명에서 무엇을 성취하려고하는지 명확하게 알 수는 없지만 루트에서 임의의 리프까지의 경로가 있는지 여부를 확인한다고 가정합니다. sum 경로 합계

출처

2017-03-27 04:17:24 wbars

이진 트리에서 경로 합계를 계산하십시오.

답변

관련 문제