一.题目介绍
1.题目来源
链接：LeetCode
2.题目
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。叶子节点是指没有子节点的节点。
二.具体实现
1.实现思路
思路就是深度优先，当树不为空时，先找到叶子节点，然后往左子树搜索再往右子树搜索，如果目标值与节点数之差为0则代表找到了符合条件的即存在，反子则不存在。
2.实现代码
1)自己的实现方式
public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) { return false; } return dfs(root, targetSum); } private boolean dfs(TreeNode root, int num) { //递归的边界 节点为null if (root.left == null && root.right == null){ return (num - root.val) == 0; } //往左子树搜索 if (root.left != null && dfs(root.left,num - root.val)){ return true; } //往右子树搜索 if (root.right != null && dfs(root.right,num - root.val)){ return true; } return false; } 复制代码
2)题友的实现方式
将其转换成求解从root.left或者root.right到叶子节点是否存在路径和为sum-root.val的路径，即 hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
3.运行结果
三.题后思考
关于二叉树的题目，深度优先和广度优先是最佳首选，其次就是利用hash或者栈的特点结合，也可以快速解决问题，另外还是没有找到之前动态二叉树的网站，估计已经没了，不然更加容易理解。
