能发朋友圈的网站建设广告语,东莞网站搜索排名,wordpress生成tags页面,台州哪里做网站一、给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
112. 路径总和 - 力扣这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
112. 路径总和 - 力扣LeetCode
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public boolean traversal(TreeNode root,int sum){if(root.leftnullroot.rightnullsum0)return true;if(root.leftnullroot.rightnullsum!0)return false;if(root.left!null){sum-root.left.val;if(traversal(root.left,sum))return true;sumroot.left.val;//回溯}if(root.right!null){sum-root.right.val;if(traversal(root.right,sum))return true;sumroot.right.val;}return false;}public boolean hasPathSum(TreeNode root, int targetSum) {if(rootnull)return false;return traversal(root,targetSum-root.val);}
} 二、给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
113. 路径总和 II - 力扣LeetCode
class Solution {public ListListInteger pathSum(TreeNode root, int targetSum) {ListListInteger resnew ArrayList();if(rootnull)return res;ListInteger pathnew LinkedList();traversal(root,targetSum,res,path);return res;}public void traversal(TreeNode root, int targetSum,ListListInteger res,ListInteger path){path.add(root.val);if(root.leftnullroot.rightnulltargetSum-root.val0)res.add(new ArrayList(path));if (root.left!null) {traversal(root.left,targetSum-root.val,res,path);path.remove(path.size()-1); // 回溯}if (root.right!null) {traversal(root.right,targetSum-root.val,res,path);path.remove(path.size()-1);}}
}
