ToB企服应用市场:ToB评测及商务社交产业平台

标题: 路径总和-112 [打印本页]

---

作者: 嚴華    时间: 2024-9-16 13:58
标题: 路径总和-112
标题形貌

给你二叉树的根节点 root 和一个表现目的和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目的和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
解题思绪

我们这题采用任何一种遍历方式都是可以的，这题同样是有回溯的头脑，如果不太懂的话可以去看看前面《求二叉树的左右路径》这一题，我们先去遍历左子树，遍历的时候如果节点的左右子树都为空说明我们已经到了叶子节点，此时我们就可以做判断了，看看是不是和我们的targetSum一致，如果不一致则它的父节点会产生回溯去遍历父节点的另一个子树，同样再去看看是否和targetSum是否一致，如果一致就可以直接填写结果，不一致则继承由它们的父节点回溯去判断另一颗子树。
代码实例

1. class Solution {
2.     public boolean judge = false;
4.     public boolean hasPathSum(TreeNode root, int targetSum) {
5.         List<Integer> list = new ArrayList<>();
6.         if(root==null){
7.             return false;
8.         }else{
9.             list.add(root.val);
10.             bianli(root, targetSum, list);
11.             return judge;
12.         }
14.     }
16.     public void bianli(TreeNode root, int targetSum, List<Integer> list) {
17.         if (root.left == null && root.right == null) {
18.             if (sum(list) == targetSum) {
19.                 judge = true;
20.                 return;
21.             }
22.         }
23.         
24.         if (root.left != null) {
25.             list.add(root.left.val);
26.             bianli(root.left, targetSum, list);
27.             list.remove(list.size() - 1);
28.         }
30.         if (root.right != null) {
31.             list.add(root.right.val);
32.             bianli(root.right, targetSum, list);
33.             list.remove(list.size() - 1);
35.         }
37.     }
39.     public int sum(List<Integer> list) {
40.         int sum = 0;
41.         for (Integer in : list) {
42.             sum += in;
43.         }
44.         return sum;
45.     }
47. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4