leetcode-112-Path Sum

2019-11-11 02:48:54

字体：大中小

来源：转载

供稿：网友

问题

题目：[Path Sum]

思路

下面的代码并不是原始问题的代码。而是改良后的问题。即求一条路径和为sum。要求必须从根开始，但是不一定到叶子结束。下面用到了回溯法，我觉得这题也是回溯法比较好的实现。回溯法肯定用到了“剪枝”，但他的关键是要回溯到上一个状态。

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool haspathSum(TreeNode* root, int sum) { if(!root) return false; int ans = 0; bool found = false; dfs( root, sum, ans, found); return found; }PRivate: void dfs(TreeNode* root, int sum, int& ret, bool& found){ if(root&&!found){ ret += root->val; if(ret == sum){ found = true; return;} else if( ret > sum ){ ret -= root->val; // backtrace return ; } else{ dfs(root->left, sum, ret, found); dfs(root->right, sum, ret, found); } } }};

或者其实你没必要这么写，睡了一晚上发现。这也不算回溯。就是参数传递的时候。不要传递引用了。

代码1

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool hasPathSum(TreeNode* root, int sum) { if(!root) return false; int ans = 0; bool found = false; dfs( root, sum, ans, found); return found; }private: void dfs(TreeNode* root, int sum, int ret, bool& found){ if(root&&!found){ ret += root->val; if(ret == sum){ found = true; return;} else if( ret > sum ) return; else{ dfs(root->left, sum, ret, found); dfs(root->right, sum, ret, found); } } }};

思路（本题）

因为要访问到最底层，所以到叶子的时候判断一下就行了。

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool hasPathSum(TreeNode* root, int sum) { if(!root) return false; int ans = 0; bool found = false; dfs( root, sum, ans, found); return found; }private: void dfs(TreeNode* root, int sum, int ret, bool& found){ if(root && !found){ ret += root->val; if(!root->left && !root->right){ if(ret==sum) found = true; return; } dfs( root->left, sum, ret, found ); dfs( root->right, sum, ret, found ); } }};

上一篇：活动选择

下一篇：列表生成器

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注