Leetcode[113]-Path Sum II

简介:

Link: https://leetcode.com/problems/path-sum-ii/

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]
]

思路:使用深度优先遍历,须要

  • 一个map。保存节点是否出栈过;
  • 一个一维数组。保存根结点到当前节点的路径;
  • 一个二维数组,保存根结点到当前叶节点的和等于给定sum的路径集合。
  • 一个栈。用来辅助深度优先遍历;

依照深度优先的遍历方式遍历。

  • 进栈的时候元素同一时候加入到一维数组中,并将该节点的map值设置为0,
  • 当节点左右节点都为空的时候。推断一维数组里面的数据和是否等于给定sum,假设等于就把它丢到二维数组中,同一时候运行下一步出栈;
  • 出栈的时候也同一时候缩小一维数组的长度,并将该节点的map值设置为1,表示该节点不能再次进栈了;

Code(c++):非递归算法:

/**
 * 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:
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        vector<vector<int> > res;
        if(root==NULL) return res;
        vector<int> nums;
        map<TreeNode *, int> visited;
        stack<TreeNode *> stk;

        TreeNode* p = root;
        nums.push_back(p->val);
        stk.push(p);
        visited[p] = 0;

        while(!stk.empty()){
            p = stk.top();
            while(p->left && visited[p] == 0){
                //this is very important to break this while
                if(visited[p->left]==1) break;
                p = p->left;
                nums.push_back(p->val);
                stk.push(p);
                visited[p] = 0;
            }
            if(!stk.empty()){
                p = stk.top();
                if(!p->left && !p->right && sumVector(nums) == sum){
                    res.push_back(nums);
                }
                if( p->right && (visited.find(p->right) == visited.end() || visited[p->right] == 0)){
                    p = p->right;
                    stk.push(p);
                    nums.push_back(p->val);
                    visited[p] = 0;
                    continue;
                }
                visited[p] = 1;
                stk.pop();
                nums.resize(nums.size()-1);
            }
        }
        return res;
    }

    int sumVector(vector<int> & nums){
        int n = nums.size();
        if( n == 0 ) return 0;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            sum += nums[i];
        }
        return sum;
    }
};

递归方法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */classpublicvector<vector<int> >intvector<vector<int> >vector<int>0returnvoidvector<vector<int> >vector<int>intintifreturnif
相关文章
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode Contest 178-1368. 使网格图至少有一条有效路径的最小代价 Minimum Cost to Make at Least One Valid Path in a Grid
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
78 0
LeetCode 329. Longest Increasing Path in a Matrix
|
Go
LeetCode 124. Binary Tree Maximum Path Sum
给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
71 0
LeetCode 124. Binary Tree Maximum Path Sum
|
Unix Python
LeetCode 71. Simplify Path
给定文件的绝对路径(Unix下的路径)字符串,简化此字符串。
91 0
LeetCode 71. Simplify Path
LeetCode 64. Minimum Path Sum
给定m x n网格填充非负数,找到从左上到右下的路径,这最小化了沿其路径的所有数字的总和。 注意:您只能在任何时间点向下或向右移动。
110 0
LeetCode 64. Minimum Path Sum
Leetcode-Easy 437. Path Sum III
Leetcode-Easy 437. Path Sum III
96 0
Leetcode-Easy 437. Path Sum III