leetcode-112-Path Sum

2019-11-11 04:02:43

字體：大中小

來源：轉載

供稿：網友

問題

題目：[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 ); } }};

上一篇：2016屆藍橋杯省賽B組第三題

下一篇：phi(int n）快速冪