算法训练（C语言版本）|112. 路径总和二叉树|leetcode

地址：
力扣
文章图片
https://leetcode-cn.com/problems/path-sum/
题目：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点是指没有子节点的节点。

示例 1：

文章图片

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

文章图片

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一、递归
存在这样的路径，从 root 到叶子的路径，对于树首先想到的就是递归
遍历到当前节点时，留给子节点路径的和 = 总和 - 当前节点值
直到满足叶子节点 - 叶子结点值 = 0

/** * Definition for a binary tree node. * struct TreeNode { *int val; *struct TreeNode *left; *struct TreeNode *right; * }; */bool hasPathSum(struct TreeNode* root, int targetSum){ if(root == NULL) return false; targetSum -= root->val; if(targetSum == 0 && root->left == NULL && root->right == NULL) return true; return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum) ; }

【算法训练（C语言版本）|112. 路径总和】方法二、层级遍历
层级遍历我们之前用过很多，这里只是把值带进去，当前节点的值即父节点值+当前节点值
这里与以往写法有点区别的是，队列是动态添加的，出队入队分别用两个指针来完成，代码更加简洁，以往方法可以参考：二叉树遍历之层序遍历

/** * Definition for a binary tree node. * struct TreeNode { *int val; *struct TreeNode *left; *struct TreeNode *right; * }; */typedef struct { struct TreeNode *node; int sum; struct TreeNode *next; }QUEUE_NODE; void createQueueNode(QUEUE_NODE **qnode, struct TreeNode *node, int sum) { *qnode = (QUEUE_NODE *)malloc(sizeof(QUEUE_NODE)); (*qnode)->node = node; (*qnode)->sum = sum; (*qnode)->next = NULL; }bool hasPathSum(struct TreeNode* root, int targetSum){ QUEUE_NODE *pop, *push; if(root == NULL) return false; // enqueue createQueueNode(&pop, root, root->val); push = pop; while(pop != NULL) { if(pop->node->left == NULL && pop->node->right == NULL && pop->sum == targetSum) return true; // enqueue left child if(pop->node->left != NULL) { createQueueNode(&push->next, pop->node->left, pop->sum + pop->node->left->val); push = push->next; }// enqueue right child if(pop->node->right != NULL) { createQueueNode(&push->next, pop->node->right, pop->sum+pop->node->right->val); push = push->next; } // dequeue pop = pop->next; }return false; }

查看更多刷题笔记