具有目標總和的Leetcode解決方案從根到葉路徑  


難度級別 容易獎學金
經常問 亞馬遜 蘋果 Facebook Microsoft微軟
算法 編碼 深度優先搜索 訪問 面試準備 力碼 力碼解決方案

二進製文件 給出整數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. 如果當前根是 空值,
    • 返回 假, 因為該節點無法提供任何幫助。
  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");
    }
}

複雜度分析  

查找具有目標總和的“根到葉”路徑的時間複雜度

上),因為在最壞的情況下該程序只能在二叉樹的一次傳遞中運行。

空間複雜度以目標總和找到從根到葉的路徑

上)。 遞歸使用輔助堆棧空間。

1