Leetcode: Path Sum

淩亂°似流年 2022-08-07 03:58 7阅读 0赞

题目：

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:  
Given the below binary tree and `sum = 22`,

5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

思路分析：

采用二叉树深度遍历即可。

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution
    {
    private:
        bool dfs(TreeNode *node, int sum, int cursum)
        {
        	if (node == NULL)
        	{
        		return false;
        	}
        
        	if (node->left == NULL && node->right == NULL)
        	{
        		return node->val + cursum == sum;
        	}
        
        	return dfs(node->left, sum, cursum + node->val) || dfs(node->right, sum, cursum + node->val);
        }
    public:
        bool hasPathSum(TreeNode *root, int sum)
        {
        	return dfs(root, sum, 0);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode64——Minimum Path Sum

LeetCode64——Minimum Path Sum 与[LeetCode63——Unique Path II][LeetCode63_Unique Path II] 类

红太狼/ 2022年08月09日 16:49/ 0 赞/ 161 阅读

相关 Path Sum II--LeetCode

题目： Given a binary tree and a sum, find all root-to-leaf paths where each path's sum

本是古典何须时尚/ 2022年08月07日 11:58/ 0 赞/ 12 阅读

相关 Path Sum--LeetCode

题目： Given a binary tree and a sum, determine if the tree has a root-to-leaf path such

浅浅的花香味﹌/ 2022年08月07日 11:58/ 0 赞/ 15 阅读

相关 Leetcode: Path Sum

题目： Given a binary tree and a sum, determine if the tree has a root-to-leaf path such t

淩亂°似流年/ 2022年08月07日 03:58/ 0 赞/ 8 阅读

相关 LeetCode-Path Sum II

题目： Given a binary tree and a sum, determine if the tree has a root-to-leaf path such t

Love The Way You Lie/ 2022年08月06日 14:10/ 0 赞/ 18 阅读

相关 LeetCode113—Path Sum II

LeetCode113—Path Sum II 原题 > Given a binary tree and a sum, find all root-to-leaf

悠悠/ 2022年07月26日 04:25/ 0 赞/ 186 阅读

相关 LeetCode112—Path Sum

LeetCode112—Path Sum 原题 > Given a binary tree and a sum, determine if the tree has

桃扇骨/ 2022年07月26日 04:25/ 0 赞/ 156 阅读

相关 [leetcode]: 112. Path Sum

1.题目 Given a binary tree and a sum, determine if the tree has a root-to-leaf path suc

野性酷女/ 2022年06月15日 11:40/ 0 赞/ 209 阅读

相关 [leetcode]: 437. Path Sum III

1.题目 You are given a binary tree in which each node contains an integer value. Find

柔光的暖阳◎/ 2022年06月15日 10:51/ 0 赞/ 157 阅读

相关 [Leetcode] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 209 阅读