LeetCode path Sum i ,ii递归和迭代解法-白红宇

LeetCode path Sum i ,ii递归和迭代解法

阅读量：4187 次

发布时间：2019-05-26

本文共 2853 字，大约阅读时间需要 9 分钟。

/********************************************************************************** * * Given a binary tree and a sum, determine if the tree has a root-to-leaf path * such that adding up all the values along the path equals the given sum.* * For example:* Given the below binary tree and sum = 22,*               5*              / \*             4   8*            /   / \*           11  13  4*          /  \      \*         7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

************************************************************************/

// Date   : 2016.07.23// Author : yqtao// https://github.com/yqtaowhu/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * };class Solution {public:bool hasPathSum1(TreeNode *root, int sum) {        if (root == NULL) return false;        if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);    }   bool  hasPathSum2(TreeNode *root, int sum){    if(!n) return false;    stack
   
     st;    TreeNode *cur = root, *pre;    while(cur || !st.empty()){        while(cur){            st.push(cur);            sum -= cur->val;            cur = cur->left;        }        cur = st.top();        if(!cur->left && !cur->right && !sum) return true;        if(cur->right && pre != cur->right) cur = cur->right;        else{            st.pop();            sum += cur->val;            pre = cur;            cur = NULL;        }    }    return false;}  };

********************************************************************************** * * Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.* * For example:* Given the below binary tree and sum = 22,* *               5*              / \*             4   8*            /   / \*           11  13  4*          /  \    / \*         7    2  5   1* * return* * [*    [5,4,11,2],*    [5,8,4,5]* ]* *               **********************************************************************************/class Solution {public:    vector
   
    
     > pathSum(TreeNode* root, int sum) {
           vector
     
      
        > paths;        vector
       
         path;        findPaths(root, sum, path, paths);        return paths;      }private:    void findPaths(TreeNode* node, int sum, vector
        
         & path, vector
         
          
            >& paths) { if (!node) return; path.push_back(node -> val); if (!(node -> left) && !(node -> right) && sum == node -> val) paths.push_back(path); findPaths(node -> left, sum - node -> val, path, paths); findPaths(node -> right, sum - node -> val, path, paths); path.pop_back(); }};