具有目标总和的Leetcode解决方案从根到叶路径  


难度级别 易得奖学金
经常问 亚马逊 Apple Facebook 微软
算法 编码 深度优先搜索 访谈 面试准备 力码 力码解决方案

二进制文件 给出整数K。 我们的目标是返回树中是否存在从根到叶的路径,以使其总和等于目标K。 路径的总和是位于该路径上的所有节点的总和。

具有目标总和的Leetcode解决方案从根到叶路径

    2
    
  /    \
  
1        4
 
       /     \

     1         4

K = 7
Path Present
     2
          
  /     \

1         4

       /     \

     1          3

K = 6
No such path

 

途径  

该方法非常简单。 我们可以检查是否在某个点上节点的值正是我们所需要的,并且它也是叶子。 然后,我们可以得出结论,存在一条从根到目标总和的路径。 因此,很直观,当我们递归地跳到任何孩子时,我们必须传递剩余的总和才能完成目标。

这个想法只适用于 .

算法  

  1. 创建一个递归辅助函数
  2. Helper函数具有当前节点的详细信息以及剩余的总和
  3. 如果当前根是 NULL,
    • 回报 假, 因为该节点无法提供任何帮助。
  4. 如果当前根是 不是NULL
    • 如果所需的总和等于节点值并且该节点是叶子
      • 返回true
    • 其他
      • 检查是否有左子树或子树满足所需的总和:current_sum – node_value
  5. 打印输出
参见
N元树Leetcode解决方案的最大深度

实施   

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");
    }
}

复杂度分析  

查找具有目标总和的“根到叶”路径的时间复杂度

上),因为在最坏的情况下该程序只能在二叉树的一次传递中运行。

空间复杂度以目标总和找到从根到叶的路径

上)。 递归使用辅助堆栈空间。