代码随想录二叉树——路径总和

题目

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 给定如下二叉树，以及目标和 sum = 22， 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路

使用递归法要确定遍历顺序，在本题中，前中后序都可以，因为不需要考虑中节点的处理顺序。

class Solution {boolean traversal(TreeNode root,int count){//直接将目标值count作为参数传入，每找到一个节点就进行减法操作if(root.left != null && root.right != null && count == 0){return true;//遇到叶子节点，并且计数为0，则找到一条满足的路径}if(root.left != null && root.right != null){return false;//不满足目标值的话直接返回}if(root.left != null){count -= root.left.val;//递归，处理节点，改变count值if(traversal(root.left,count)) return true;count += root.left.val;//回溯，撤销处理结果，恢复count值}if(root.right != null){count -= root.right.val;if (traversal(root.right, count)) return true;count += root.right.val;}return false;}public boolean haspathsum(TreeNode root,int sum){if(root ==null){return false;}return traversal(root,sum - root.val);}}//精简后的代码class solution {public boolean hasPathSum(TreeNode root, int sum) {if (root == null) return false;if (root.left != null && root.right != null && sum == root.val) {//如果是叶子结点，并且节点等于目标值return true;//则返回true}//求两侧分支的路径和return haspathsum(root.left, sum - root.val) || haspathsum(root.right, sum - root.val);}};