剑指 Offer 34. 二叉树中和为某一值的路径

题目

剑指 Offer 34. 二叉树中和为某一值的路径

我的思路

我的思路与官方题解有出入，不够简练。

先概述一下我的做法：先序递归遍历树，参数中除了传递当前节点外还包括当前路径和。因为递归函数的调用栈隐式存储了路径信息，所以当找到满足要求的路径并返回时，可以借助递归函数的返回值传递是否找到了满足要求的路径，并且是哪些路径的信息。这个返回参数是一个列表，元素是满足条件的路径。如果当前节点为叶子节点并且路径和满足要求，那么为该列表添加一个项，并把叶子节点val加入新的一项；如果不满足要求，那么返回一个空的列表；递归函数在返回前还需要处理本层调用的所有递归返回值，把本节点的val添加到已存在的路径中去。

官方题解的思路更简洁，概述如下：

用一个全局变量列表存储当前已有的满足条件的路径，一个全局变量向量来存储当前路径。在遍历树的过程中，随时通过pop_back和push_back，来更新当前路径。并在访问叶子节点时判断路径和是否满足要求。如果满足要求，把当前路径加入到全局变量结果列表中即可。实现见拓展学习

两种思路复杂度相同

时间复杂度 O(N) ： N 为二叉树的节点数，先序遍历需要遍历所有节点。
空间复杂度 O(N) ：最差情况下，即树退化为链表时，path 存储所有树节点，使用 O(N)额外空间。

我的实现

class Solution {
public:
    vector<vector<int>> PATHS;
    int SUM;
    int visit(TreeNode *root,int preSum){
        if(root!=NULL){
            if(preSum+root->val==SUM){
                int no = PATHS.size();
                vector<int> temp;
                PATHS.push_back(temp);
                return no;
            }
            return -1;
        }return -1;
    }

    vector<int> search(TreeNode *root,int preSum){
               
        vector<int> paths;
        if(root==NULL)return paths;
        if(root!=NULL){
            if(root->left==NULL&&root->right==NULL)
            paths.push_back(visit(root,preSum));
            vector<int> temp1 = search(root->left,preSum+root->val);        
            paths.insert(paths.end(),temp1.begin(),temp1.end());
            temp1 = search(root->right,preSum+root->val);
            paths.insert(paths.end(),temp1.begin(),temp1.end());
        }
        for(auto it:paths){
            if(it>=0){
                PATHS[it].push_back(root->val);               
            }
        }
        
        vector<int>::iterator iter = paths.begin();
        while(iter!=paths.end()){
            if(*iter <0){
                paths.erase(iter);
            }else{
            iter++;}
        }
        return paths;

    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        SUM = sum;
        search(root,0);
        vector<vector<int>> result;     
        for(auto it:PATHS){
            vector<int> temp;
            
            for(vector<int>::iterator it2 = it.end();it2!=it.begin();){
                it2--;
                temp.push_back(*it2);
            }
            result.push_back(temp);
        }
        return result;
    }
};

拓展学习

/**
 * 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> > res;
    vector<int> path;
    //回溯算法
    void dfs(TreeNode* root,int sum){
        if(root==nullptr) return;
        //先序遍历
        path.push_back(root->val);
        sum -= root->val;
        if(sum == 0 && root->left ==nullptr && root->right == nullptr){
            res.push_back(path);
        }
        dfs(root->left,sum);
        dfs(root->right,sum);
        path.pop_back();//最后回溯
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root,sum);
        return res;
    }
};

作者：ni-hen-you-xiu-2
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/c-xian-xu-jia-hui-su-by-ni-hen-you-xiu-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。