Amazon 인터뷰 질문을 해결하여 잎 숫자에 루트 합계

질문: 0-9의 숫자만 포함하는 이진 트리가 주어지면 각 루트-리프 경로는 숫자를 나타낼 수 있습니다.

예를 들어 숫자 123을 나타내는 루트-리프 경로 1->2->3이 있습니다.

루트에서 리프까지의 모든 수의 총합을 구하십시오.

예:

         1
        / \
       2   3

위 트리의 경우,
경로 1 = 1 -> 2 = 12
경로 2 = 1 -> 3 = 13
출력은 12 + 13 = 25입니다.

질문만 읽어도 트리를 순회해야 한다고 할 수 있는데, 부모->자식 관계가 유지되도록 순회를 해야 합니다.

Depth First Traversal은 노드를 선택하고 역추적하기 전에 각 분기를 따라 가능한 한 멀리 탐색하는 순회 유형입니다.

Wikipedia의 애니메이션:


코드로 변환:

   dfs(node){
       if(node == null) return;

       // do something

       dfs(node.left);
       dfs(node.right);
   }

다음은 현재 노드에서 값을 처리하는 방법입니다. 자세히 보면 각 수준에서 이전 수준 결과에 10을 곱하고 현재 노드 수준에서 값을 더합니다.
이 같은 :

  dfs(node,prev){
      if(node == null) return;

      let curr = prev * 10 + node.val;

      dfs(node.left,curr);
      dfs(node.right,curr);

호출 스택에 대한 정보:

여기에서 우리는 재귀적으로 dfs를 호출하고 있으므로 각 호출에 대해 루트 -> 현재 노드 값을 추적하는 별도의 호출 스택이 유지되며 다른 노드의 루트 -> 노드 값은 별도의 호출 스택에 존재하므로 간섭하지 않습니다. . 이것을 더 잘 이해하려면 끝에 있는 애니메이션을 참조하십시오.

마지막 장애물은 계산된 값을 반환하는 방법입니다.

우리는 리프 노드가 왼쪽 및 오른쪽 자식이 null 인 노드라는 것을 알고 있습니다. 이것이 특정 하위 트리 경로에 대한 루트 -> 리프 값을 반환하는 단서입니다.

    if(root.left == null && root.right == null) 
       return prev*10 + node.val;

내부 노드를 만나면 왼쪽 및 오른쪽 하위 트리에서 반환된 값을 더하여 반환합니다.

     return dfs(root.left,curr) + return dfs(root.right,curr);

각 단계 시각화:


모든 것을 코드로 정리:

var sumNumbers = function(root) {
    return dfs(root,0);
};

function dfs(node,prev){
    if(node == null) return 0;
    if(node.left == null && node.right == null){
        return prev*10 + node.val;
    }

    let curr = prev*10 + node.val;

    return dfs(node.left,curr) + dfs(node.right,curr);
}

제 설명이 마음에 드셨으면 좋겠습니다 :D

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/rootToleaf.js