대상 합계가있는 루트에서 리프 경로로 Leetcode Solutions

난이도 쉽게
자주 묻는 질문 아마존 Apple Facebook Microsoft
알고리즘 코딩 깊이 우선 검색 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 나무조회수 21

바이너리 나무 정수 K가 주어집니다. 우리의 목표는 트리에 루트-투-리프 경로가 있는지 여부를 반환하여 합계가 target-K와 동일하도록하는 것입니다. 경로의 합은 경로에있는 모든 노드의 합입니다.

대상 합계가있는 루트에서 리프 경로로 Leetcode Solutions

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

접근

접근 방식은 매우 간단합니다. 특정 지점에서 노드의 값이 우리가 필요로하는 것이고 리프이기도한지 확인할 수 있습니다. 그런 다음 루트에서 목표 합계가있는이 지점까지 경로가 존재한다고 결론을 내릴 수 있습니다. 따라서 우리가 재귀 적으로 임의의 자식으로 점프 할 때 목표를 완료하기 위해 나머지 합계를 전달해야한다는 것은 직관적입니다.

이 아이디어는 나무.

암호알고리즘

  1. 재귀 도우미 함수 만들기
  2. 도우미 함수에는 현재 노드 세부 정보와 나머지 합계가 있습니다.
  3. 현재 루트가 Null
    • 반환 그릇된, 이 노드는 아무것도 기여할 수 없기 때문입니다.
  4. 현재 루트가 NULL 아님
    • 필요한 합계가 노드 값과 같고 노드가 리프 인 경우
      • 참을 돌려 주다
    • 그렇지 않으면
      • 왼쪽 또는 자식 하위 트리가 필요한 합계를 사용하여 요구 사항을 충족하는지 확인합니다. current_sum – node_value
  5. 출력 인쇄

실시

타겟 합계로 루트에서 리프 경로를 찾는 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

bool pathSumEqualToTarget(treeNode* root , int target)
{
    if(!root)
        return false;
    if(target == root->value && !root->left && !root->right)
        return true;
    return pathSumEqualToTarget(root->left , target - root->value) || pathSumEqualToTarget(root->right , target - root->value);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right =  new treeNode(4);
    root->right->left = new treeNode(1);
    root->right->right = new treeNode(4);

    int K = 7;

    if(pathSumEqualToTarget(root , K))
        cout << "Path Present" << '\n';
    else
        cout << "No such path" << '\n';

}

 

대상 합계로 루트에서 리프 경로를 찾는 Java 프로그램

class treeNode
{
    int value;
    treeNode left , right;

    public treeNode(int x)
    {
        value = x;
        left = right = null;
    }
}

class path_sum
{
    public static boolean pathSumEqualToTarget(treeNode root , int target)
    {
        if(root == null)
            return false;
        if(root.value == target && root.left == null && root.right == null)
            return true;
        return pathSumEqualToTarget(root.left , target - root.value) || pathSumEqualToTarget(root.right , target - root.value);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(4);
        root.right.left = new treeNode(1);
        root.right.right = new treeNode(4);

        int K = 7;

        if(pathSumEqualToTarget(root , K))
            System.out.println("Path Present");
        else
            System.out.println("No such path");
    }
}

복잡성 분석

목표 합계로 루트에서 리프 경로를 찾기위한 시간 복잡성

의 위에), 최악의 경우 프로그램이 이진 트리의 단일 패스에서 작동하기 때문입니다.

목표 합계로 루트에서 리프 경로를 찾기위한 공간 복잡성

의 위에). 재귀는 보조 스택 공간을 사용합니다.

코멘트를 남겨

Translate »
1