[LeetCode]113.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]
]

【分析】

题目要求求出所有路径结果。在求出左子树满足结果时，不能return，而是继续求右子树。

每到一个叶子节点判断是否满足结果，如果满足添加路径集合paths中，如果不能满足结果，把该节点从路径path中删除。

【代码】

/*********************************
*   日期：2015-01-02
*   作者：SJF0115
*   题目: 113.Path Sum II
*   来源：https://oj.leetcode.com/problems/path-sum-ii/
*   结果：AC
*   来源：LeetCode
*   博客：
*   时间复杂度：O(n)
*   空间复杂度：O(logn)
**********************************/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 二叉树节点
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<int> path;
        // 多条路径
        vector<vector<int> > paths;
        if (root == NULL){
            return paths;
        }//if
        pathSum(root,sum,path,paths);
        return paths;
    }
private:
    void pathSum(TreeNode *root, int sum,vector<int>& path,vector<vector<int> >& paths) {
        // 当前节点添加到路径中
        path.push_back(root->val);
        int cur = sum - root->val;
        // 判断是否找到一条root-to-leaf路径和等于sum
        if(root->left == NULL && root->right == NULL && cur == 0){
            paths.push_back(path);
        }//if
        // left sub-tree
        if(root->left){
            pathSum(root->left,cur,path,paths);
            // 回溯上层节点删除当前节点
            path.pop_back();
        }//if
        // right sub-tree
        if(root->right){
            pathSum(root->right,cur,path,paths);
            // 回溯上层节点删除当前节点
            path.pop_back();
        }//if
    }
};
// 创建二叉树
TreeNode* CreateTreeByLevel(vector<int> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

int main() {
    Solution solution;
    // -1代表NULL
    vector<int> num = {5,4,8,11,-1,13,4,7,2,-1,-1,5,1};
    TreeNode* root = CreateTreeByLevel(num);
    vector<vector<int> > paths = solution.pathSum(root,22);
    for(int i = 0;i < paths.size();i++){
        for(int j = 0;j < paths[i].size();j++){
            cout<<paths[i][j]<<" ";
        }
        cout<<endl;
    }
}