leetcode: 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.

通过一个p指针,遍历 二叉树,并将每次的值 保存在 sum2 中 。

遇到右节点,将右节点+depth 保存在 temp中,当再次使用 该节点时,根据depth 将sum2中的长度削减成 depth-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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> re;
        if(root==NULL) return re;
        TreeNode *p=root; int depth=1;
        vector<pair<TreeNode * ,int>>  temp;             // 保存右节点+depth
        vector<int> sum2;                                // 保存一条路径的所有点值
        pair<TreeNode *, int > t=make_pair(root,depth);
       // temp.push_back(t);
        while(!temp.empty()||p!=NULL){
            sum2.push_back(p->val);
            if(p->left!=NULL){
                if(p->right!=NULL){
                    temp.push_back(make_pair(p->right,depth+1));
                }
                p=p->left;
                depth++;
            }
            else{
                if(p->right==NULL){
                    int result=0;
                    for(int i=0;i<sum2.size();i++)
                    {
                        result=result+sum2[i];
                    }
                    if(result==sum)
                        re.push_back(sum2);
                    if(temp.empty()) break;
                    p=(*(temp.end()-1)).first;
                    depth=(*(temp.end()-1)).second;
                    temp.erase(temp.end()-1);
                    sum2.erase(sum2.begin()+depth-1,sum2.end());
                }
                else{
                p=p->right;
                depth++;
                }
            }
        }
        return re;
    }
};
时间: 05-14

leetcode: Path Sum II 迭代法的相关文章

LeetCode——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] ] 给定一个二叉树和一个值,找出所有根到叶的路径和等于

LeetCode: Path Sum II [113]

[题目] 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] ] [题意] 判断二叉树中是否存在一条从根到

LeetCode: Path Sum II 解题报告

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] ] SOLUTION 1: 使用

[Leetcode] 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 andsum = 22, 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ] 题意:给定一数,在树中找出所有路径和等于该数的情况.方

[leetcode]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] ] 分析: 这道题目算是Path Sum的延伸,只不过

[LeetCode] 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] ] Hide Tags Tree Depth-first

LeetCode Path Sum II (DFS)

题意: 给一棵二叉树,每个叶子到根的路径之和为sum的,将所有可能的路径装进vector返回. 思路: 节点的值可能为负的.这样子就必须到了叶节点才能判断,而不能中途进行剪枝. 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL)

【Leetcode】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] ] 思路:与[Leetcode]Path Sum 不同

Path Sum II leetcode java

题目: 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] ] 题解: 这道题除了要判断是否有这样的一个p