来源:力扣(LeetCode)

链接:113. 路径总和 II

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明:叶子节点是指没有子节点的节点。

示例:

给定如下二叉树,以及目标和 sum = 22:

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

二、题解

说明:

此题是112. 路径总和Ⅰ的升级版(题解参考:),相对于第一题来说,有以下两点不通:

  1. 题Ⅰ只需要判断存在即可,该题需要找到所有可能的结果。
  2. 找到所有结果的同时,该题还需要保存所有的路径。

算法:

递归+深搜遍历所有的树节点,每遍历一个节点除了计算sum是否满足条件以外,还要记录下该节点。当遇到满足条件的叶节点,把当前路径加到结果中去。需要利用到两个辅助的数组。

代码:

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return m_ans;
    }
private:
    void dfs(TreeNode *root, int sum) {
        if(root == NULL) {
            return;
        }

        // 节点添加到临时的数组里面去
        m_vec.push_back(root->val);
        sum -= root->val;

        if (root->left == NULL && root->right == NULL && sum == 0) {
            // 当前临时数组加入到结果数组中
            m_ans.push_back(m_vec);
        }

        // 遍历左节点
        if (root->left) {
            dfs(root->left, sum);
        }
        
        // 遍历右节点
        if (root->right) {
            dfs(root->right, sum);
        }
        
        // 最关键的一步:回溯状态
        // 函数入口处把当前节点添加到临时数组里面去了,这里退出的时候要删掉这一个节点
        // 避免当前节点还存在于临时数组中,影响后续的遍历结果
        m_vec.pop_back();
    }

    vector<vector<int>> m_ans; // 保存所有的结果
    vector<int> m_vec; // 临时保存路径的数组
};

复杂度分析:

  • 时间复杂度:访问每个节点一次,时间复杂度为O(N) ,其中N是节点个数。
  • 空间复杂度:需要用到两个数组,其中一个是保存结果的数组可不算入空间占用,另外一个保存路径的临时数组最坏情况下(树是一条线,即类似链表的时候)占用O(N) ,平均和最优情况下(树是平衡树)占用O(log(N))。
最后修改:2019 年 12 月 14 日
喜欢就给我点赞吧