대상 합계가있는 루트에서 리프 경로로 Leetcode 솔루션-TutorialCup

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

핀

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7

Path Present

     2
          
  /     \

1         4

       /     \

     1          3

K = 6

No such path

차례

접근

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

이 아이디어는 나무.

암호알고리즘

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

실시

타겟 합계로 루트에서 리프 경로를 찾는 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");
    }
}

복잡성 분석

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

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

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

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

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

접근