题解 | #二叉树中和为某一值的路径(一)#
二叉树中和为某一值的路径(一)
https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c
1 解题思路
二叉树的链式存储结构很容易想到递归法:
首先确定递归结束条件:已到达叶子结点,判断当前分支数值和是否与给定sum相等。相同返回true,不同返回false。
再确定递归子问题:若当前结点有左孩子,则将当前结点值累加到 部分和(part_sum) 作为子问题的参数;有右孩子同理。
假设在左子树已经找到一个分支与给定sum相同,引入剪枝的思想,如果左子树返回结果为true,无需再进入右子树寻找。
2 代码
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool solver(TreeNode* root,int part_sum,int sum){ if(!root->left && !root->right){ //到达叶子结点,进行比较并结束递归。 if((part_sum+root->val)==sum) return true; else return false; }else{ //当前结点不是叶子结点,继续向下探索叶子结点。 bool left_val=false; bool right_val = false; if(root->left){ left_val = solver(root->left,part_sum+root->val,sum); } if(!left_val && root->right){ //只有左子树中所有分支都不等于sum,才进入右子树寻找;否则跳过节省搜索时间。 right_val = solver(root->right,part_sum+root->val,sum); } return left_val || right_val; } } bool hasPathSum(TreeNode* root, int sum) { if(!root) return false; return solver(root,0,sum); } };