一、归并排序

归并排序的思想是：依次把数组分成若干个小组进行排序，然后逐步把每个小组进行排序合并。

最经典的介绍归并排序的示例图为：

第一步：把8个元素分别分成4个小组排序，得到1, 2/3, 4/5, 6/7, 8四组。

第二步：把1, 2和3, 4合并，5, 6和7, 8合并，得到1, 2, 3, 4和5, 6, 7, 8两组。

第三部：把剩下的两组合并，得到有序的数组1 2 3 4 5 6 7 8，排序完成

归并排序的时间复杂度为O(lgn)

二、合并两个有序数组

合并两个有序数组需要用到一个辅助数组，保存排序后的元素。具体的逻辑是：分别使用两个指针，指向两个数组的首端，比较两个指针指向的元素，把小的放到辅助数组里面，指针后移，重复上面的操作。

例如上面合并1, 2, 3, 4和5, 6, 7, 8两组元素，设置指针i和j分别指向两个数组，此时a[i] > b[j]，把b[j]放到数组里面去：

然后依次执行，直到b数组中的元素放完：

再把a中所有的元素放到有序数组中去，排序就完成了：

合并部分的代码：

// mid是i的结束位置，right是j的结束位置，tmp是临时数组
while (i <= mid && j <= right) {
    if (data[i] <= data[j])
        tmp[k++] = data[i++];
    else
        tmp[k++] = data[j++];
}

三、归并排序实现

/*
 * @data 待排序数组
 * @tmp 临时数组
 * @left 当前需要排序的区间开始
 * @right 当前需要排序的区间结束
 */
static void _merge_sort(int *data, int *tmp, uint left, uint right) {
    uint mid, i, j, k, cur;
    if (left == right)
        return;

    mid = (left + right) / 2;
    i = left;
    j = mid + 1;
    k = left;
    
    // 分组排序
    _merge_sort(data, tmp, left, mid);
    _merge_sort(data, tmp, mid + 1, right);

    // 合并有序分组
    while (i <= mid && j <= right) {
        if (data[i] <= data[j])
            tmp[k++] = data[i++];
        else
            tmp[k++] = data[j++];
    }

    // 处理两个数组多余的元素
    while (i <= mid)
        tmp[k++] = data[i++];
    while (j <= right)
        tmp[k++] = data[j++];

    // 拷贝已经排好序的到正式需要排序的数组
    for (i = left; i <= right; i++)
        data[i] = tmp[i];
}

/*
 * @data 待排序数组
 * @len 数组长度
 */
void merge_sort(int *data, const uint len) {
    // 为临时数组分配空间
    int *tmp = malloc(sizeof(int) * len);
    if (tmp == NULL)
        return;

    _merge_sort(data, tmp, 0, len - 1);

    // 删除临时数组的空间
    free(tmp);
    tmp = NULL;
}

一、计数排序

其基本思想为：假设n个输入的元素中的每一个都是在0到k之间的一个整数，对于每一个输入元素x，确定小于x的元素个数，直接把x放在它输出的数组中的位置上。例如有17个元素小于x，则x就应该在数组的第18个位置上。当有几个元素相同时，这一方案就要略作修改，不能都放在同一个位置上。

计数排序需要提供两个辅助数组用来计数，一个用来保存已经排好序的元素，一个用来保存每个元素在数组中出现的次数。计数排序是不稳定的排序算法，时间复杂度(n)，空间复杂度是O(n + k)，其中k是排序数组元素的范围。

例如以下数组A：

在通过计数后，得到的辅助数组C为：

对于元素1而言，它前面有两个0，因此排序后它的位置在第三个，即下标为2的位置上，但是它的数量为0，就不应该给他排序。而元素2是有的，它的位置应该是0的数量和1的数量（如果有元素1的话）之和的后面一位，在这里是第3位，下标为2。这里类似斐波那契数列：每个元素都等于前面两个的和。

因此，有必要对辅助数组C做处理，设置其所在的位置为前面所有元素数量之和，这样就不用每次都重新计算前面的数量了（参考斐波那契数列计算）：

要注意的是，对于2这个元素来说，它出现了两次，如果不做特殊处理，它们处的位置都是第四个位置。要想办法把两个2分别放到自己合适的位置上去。可以采取的办法是从后往前排序，每排完一个数字，当前数字的值减一。

图例：

第一步，A的最后一个元素是3，得到C[3]的值为7，把3先放到第7个位置，并把C[3]的值减一：

第二步，现在A的最后一个元素（未排序的）是0，得到C[0]为2，放到第二个位置，C[0]减一：

第三步，重复以上步骤，直到A中所有的元素都排序完毕：

此时，整个数组就是有序的了。

二、计数排序的代码实现

// 数据可能出现的最大值
const unsigned int max_val = 100;
void count_sort(int data[], const unsigned int n) {
    // 计数数组
    int cnt[max_val] = {0};
    // 生成辅助数组
    int *tmp = new int[n];
    unsigned int i;

    // 初始化计数数组
    for (i = 0; i < n; i++) {
        cnt[data[i]]++;
    }

    // 累加所有的数量
    for (i = 1; i < max_val; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 计数排序
    for (i = n - 1; i >= 0 && i < n; i--) {
        tmp[cnt[data[i]] - 1] = data[i];
        cnt[data[i]]--;
    }

    // 拷贝辅助数组到排序数组
    for (i = 0; i < n; i++) {
        data[i] = tmp[i];
    }
}

一、堆排序原理

通过最大堆的性质可以知道：一个堆中最大的元素总是在堆顶的，即数组下标0的位置。基于这一点，我们可以每次都把堆中的最大值提取出来，放到当前数组的后面。然后重新构建最大堆，重复这个过程，以此来完成一个数组的排序。

例如，一个已知的最大堆为：

把最大的元素16提取出来，放到最后。然后重新建堆，此时堆中最大的元素为15，更新后的堆为：

再把15提取出来，重新建堆，得到：

如此往复，直到最后堆中的元素只有一个，就完成了整个数组的排序。

二、代码实现

堆排序的关键点在于构造堆，如何构造堆可参考数据结构之堆。基于模板的最大堆化函数实现：

template <typename T>
static void max_heapify(T *data, size_t len, size_t idx) {
    size_t largest, lchild, rchild;

    lchild = LCHILD(idx);
    rchild = RCHILD(idx);

    if (lchild < len && data[lchild] > data[idx])
        largest = lchild;
    else
        largest = idx;

    if (rchild < len && data[rchild] > data[largest])
        largest = rchild;

    if (idx != largest) {
        my_swap(data[idx], data[largest]);
        max_heapify(data, len, largest);
    }
}

实现堆排序，堆排序的关键点在于从后往前排：

template <typename T>
static void heap_sort(T *data, size_t len) {
    size_t i, mid;
    mid = len / 2;

    // 建堆
    for (i = mid - 1; i >= 0 && i < len; i--) {
        max_heapify(data, len, i);
    }

    // 堆排序，从后往前
    for (i = len - 1; i >= 1; i--) {
        my_swap(data[i], data[0]);
        max_heapify(data, --len, 0);
    }
}

时间复杂度

堆排序的时间主要消耗再建堆上面，每次拿掉一个元素之后，都重新执行最大堆化。

每次构造最大堆的时间复杂度为O(log(n))，因此堆排序的总时间复杂度为n(log(n))，n代表元素个数。

一、堆

堆是一种数据结构，通常通常所说的堆即二叉堆。二叉堆是一个数组，可以被看成一个完全二叉树，如下图所示：

他在数组中的表现形式为：

通过数组很容易得到每个父节点和其子节点的关系，假设数组的起始下标为0，那么有：

PARENT(i) = (i - 1) / 2  --> 如下标1和2的数组元素，其父节点是下标0的元素。
LEFT_CHILD(i) = (i * 2) + 1   
RIGHT_CHILD(i) = (i * 2) + 2  -->如下标为0的数组元素，其左右子节点的下标分别是1和2。

因此可以直接在程序中定义：

#define PARENT(i) ((i - 1) >> 1)
#define LEFT_CHILD(i) (((i) << 1) + 1)
#define RIGHT_CHILD(i) (((i) << 1 ) + 2)

二、最大堆和最小堆

堆有最大堆和最小堆之分，在最大堆中，除了根节点以外的所有节点i都要满足：A[PARENT[i]] >= A[i]，所有的子节点的值不会超过其父节点的值。因此，在最大堆中，最大的元素存放在根节点中。

而最小堆和最大堆相反，除了根节点以外的所有节点i都要满足：A[PARENT[i]] <= A[i]， 所有子节点的值都大于等于其根节点的值。因此，最小堆中根节点的元素是最小的。

在堆排序算法中，使用的是最大堆，最小堆通常用于构造优先级队列。

以最大堆为例，其包含的操作为：

• MAX_HEAPIFY：用来维护一个最大堆。
• BUILD_MAX_HEAP：从一堆无序的数组中构造出一个最大堆。
• HEAPSORT：执行一次堆排序过程。

三、最大堆

3.1 维护最大堆

把一个堆构造成最大堆的流程：

1. 从A[i], A[LEFT[i]], A[RIGHT[i]]中选出最小的，保存其下标largest
2. 如果largest不等于i，交换A[i]和A[largest]

以下图为例，当前堆中4处于一个非正确的位置：

首先把4和其儿子中最大的14交换，得到以下堆：

交换后4依旧不是最小的元素，继续交换4和8：

4当前已经是叶子节点了，此时对4的最大堆化操作就完成了。并且此时的堆也就是一个最大堆。

不难看出：对一个高度为h的树来说，这个操作的时间复杂度为O(h)。

对应的c代码：

static void _max_heapify(int *data, const uint len, const uint i) {
    unsigned int lchild, rchild;
    unsigned int largest;

    lchild = LEFT_CHILD(i);
    rchild = RIGHT_CHILD(i);

    // 得到父子节点中最小的元素
    if (lchild < len && data[i] < data[lchild])
        largest = lchild;
    else
        largest = i;

    if (rchild < len && data[largest] < data[rchild])
        largest = rchild;

    // 交换最小的元素
    if (i != largest) {
        swap_int(&data[i], &data[largest]);
        _max_heapify(data, len, largest);
    }
}

3.2 建堆

建堆的过程实际上是执行多次MAX_HEAPIFY，我们只需对2/n以内的元素都执行MAX_HEAPIFY操作即可完成一个最大堆的构建。

因为[n/2, n)之间的元素都是叶子节点，所以无需对它们进行转换操作。

要注意的是建堆必须从下往上，否则可能出现堆只是局部有效，对全局而言并非有效：

以上图为例，如果从上到下建堆，在调整完4的位置之后，14被放在了树根。而实际上被放在树根的应该是16，因为接下来就不会调整14了，它的位置就永远不对，这个堆也就不是一个符合要求的堆。

代码：

static void _build_max_heap(int *data, const uint len) {
    int i;
    for (i = (len / 2) - 1; i >= 0; i--) {
        _max_heapify(data, len, i);
    }
}

四、堆排序

参考：排序算法之堆排序

题目要求：随机输出100以内的不重复数字

解法一：暴力求解

最简单也最容易想到的解法：

1. 创建含有100个元素的数组data[100]，全部置零
2. 生成100以内的随机数r
3. 如果data[r]等于0，设置data[r]=1
4. 如果data[r]等于1，重复第二步

此算法的时间复杂度为O(n^2)，越到后面，碰撞的机会也越来越大，最坏的情况下，时间复杂度远不止O(n^2)。

解法二：Fisher-Yates shuffle洗牌算法

算法的逻辑为：

1. 创建一个长度为n的数组（假设下标从1开始），每个元素的值都置为其下标
2. 设max=n，从n开始到1逐步递减
3. 生成[1, max]之间的随机数r，把data[r]和data[max]交换，max减一
4. 重复第三步，直到max小于1

2.1 过程图解

假设要生生十个随机数，创建十个元素的数组，初时时的状态为：

+--+--+--+--+--+--+--+--+--+--+
| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+
                             ^
                            max   

逐步生成随机数的过程：

max = 10, r = 3
        +--------------------+
        v                    v
+--+--+--+--+--+--+--+--+--+--+
| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+

max = 9, r = 7
                    +-----+
                    v     v
+--+--+--+--+--+--+--+--+--+--+
| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+

max = 8, r = 1
  +--------------------+
  v                    v
+--+--+--+--+--+--+--+--+--+--+
| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+

max = 7, r = 5
              +-----+
              v     v
+--+--+--+--+--+--+--+--+--+--+
| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+

...

2.2 代码实现

void shuffle(int *data, int n) {
    int i, r;
    for (i = 0; i < n; i++) {
        data[i] = i;
    }
    for (i = n; i > 0; i--) {
        r = rand() % n;
        swap(&data[r], &data[i - 1]); // 交换
    }
}

单测案例：

TEST(SHUFFLE_TEST, FEATURE_TEST) {
    int i, data[TEST_NODE_COUNT], verify[TEST_NODE_COUNT];
    shuffle(data, TEST_NODE_COUNT);
    memset(verify, 0, sizeof(int) * TEST_NODE_COUNT);
    for (i = 0; i < TEST_NODE_COUNT; i++) {
        verify[data[i]] ++;
    }
    for (i = 0; i < TEST_NODE_COUNT; i++) {
        ASSERT_EQ(verify[i], 1) << verify[i];
    }
}

int main(int argc, char **argv) {
    srand(time(NULL));

    testing::InitGoogleTest(&argc, argv);

    RUN_ALL_TESTS();
    return 0;
}

一、基本排序算法

1. 插入排序
2. 选择排序
3. 冒泡排序
4. 梳排序

二、高级排序算法

1. 快速排序
2. 堆排序
3. 计数排序
4. 归并排序

三、各排序算法的比较

各排序算法总结

关于斐波那契数列的描述：
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

一、面试题

求斐波那契数列的第n项：写一个函数，输入n，输出斐波那契数列的第n项。

二、解法一

求斐波那契数列最简单的解法就是用递归，大部分书籍上介绍递归的时候都会用斐波纳契数列做例子，递归很容易写：

long long Fibonacci_Solution1(unsigned int n)
{
    if(n <= 0)
        return 0;

    if(n == 1)
        return 1;

    return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
}

这个解法并不是最优的，因为中间充斥了很多重复的运算，应该还不足以应付面试。例如计算f(10)的过程中：

f(6)/f(7)/f(8)都被计算了多次，当数据越大时，重复计算的次数也越来越多，因此并不是最优的解法。

三、解法二

上面的递归之所以慢，是因为重复的计算太多，我们可以考虑从如何减少重复计算下手。例如可以选择从2开始，保存前两位的值，依次向后计算：

long long Fibonacci_Solution2(unsigned n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    long long  fibNMinusOne = 1;
    long long  fibNMinusTwo = 0;
    long long  fibN = 0;
    for(unsigned int i = 2; i <= n; ++ i)
    {
        fibN = fibNMinusOne + fibNMinusTwo;

        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }

     return fibN;
}

注意事项：传参的n的类型为unsigned int，保存值以及返回值的数据类型是long long，避免int溢出。

ps：虽然long long也会溢出，至少比int大一些。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/add-two-numbers

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

一、题目描述

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字0之外，这两个数都不会以0开头。

示例：

• 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
• 输出：7 -> 0 -> 8
• 原因：342 + 465 = 807

二、题解

思路：

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。：

算法：

就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表l1和l2的表头开始相加。由于每位数字都应当处[0, 9]的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5 + 7 = 12。在这种情况下，我们会将当前位的数值设置为2，并将进位carry = 1带入下一次迭代。进位carry必定是0或1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9 + 9 + 1 = 19。

伪代码如下：

• 将当前结点初始化为返回列表的哑结点。
• 将进位carry初始化为 00。
• 将p和q分别初始化为列表l1和l2的头部。

• 遍历列表l1和l2直至到达它们的尾端。

  • 将x设为结点p的值。如果p已经到达l1的末尾，则将其值设置为0。
  • 将 y设为结点q的值。如果q已经到达 l2l2 的末尾，则将其值设置为0。
  • 设定sum = x + y + carry。
  • 更新进位的值，carry = sum / 10。
  • 创建一个数值为 (sum % 10) 的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。
  • 同时，将 pp 和 qq 前进到下一个结点。
• 检查carry = 1是否成立，如果成立，则向返回列表追加一个含有数字 11 的新结点。
• 返回哑结点的下一个结点。

请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。

特别注意以下情况：

1. 当一个列表比另一个列表长时
2. 当一个列表为空时，即出现空列表
3. 求和运算最后可能出现额外的进位，这一点很容易被遗忘

三、代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *rs, *p, *q, *cur;
        int carry = 0, sum, x, y;

        rs = new ListNode(0);
        cur = rs;

        p = l1;
        q = l2;

        // [1] 注意循环终止的条件是两个链表都不为空了才停止
        while (p || q) {
            // [2] 注意p或者q等于NULL的清情况
            x = p ? p->val : 0;
            y = q ? q->val : 0;

            // [3] 注意加上进位
            sum = x + y + carry;

            cur->next = new ListNode(sum % 10);
            carry = sum / 10;

            // [4] 注意处理p或q节点等于NULL的情况
            p = p ? p->next : NULL;
            q = q ? q->next : NULL;
            cur = cur->next;
        }

        // [5] 注意最后的进位
        if (carry) {
            cur->next = new ListNode(carry);
        }
        
        // [6] 返回rs的下一个节点
        return rs->next;
    }
};

复杂度分析：

• 时间复杂度：O(max(m,n))，假设m和n分别表示l1和 l2的长度，上面的算法最多重复max(m,n)次。
• 空间复杂度：O(max(m,n))， 新列表的长度最多为max(m,n)+1。

来源：力扣（LeetCode）

链接：581. 最短无序连续子数组，
著作权归领扣网络所有。

一、题目描述

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9] > 进行升序排序，那么整个表都会变为升序排序。

说明 :

1. 输入的数组长度范围在[1, 10,000]。
2. 输入的数组可能包含重复元素，所以升序的意思是<=。

二、题解

官方解析

2.1 排序

算法分析

对数组进行排序，将未排序数组和已排序的数组对比。数组两端朝中间遍历，找到最左边和最右边的不匹配元素，中间的元素就是无序的数组范围。

代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int i, j;

        // 建立辅助数组
        vector<int> sortNums(nums);
        // 排序
        sort(sortNums.begin(), sortNums.end());

        // 找到
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] != sortNums[i]) {
                break;
            }
        }

        // 考虑数组已全部有序的情况
        if (i == nums.size()) {
            return 0;
        }

        for (j = nums.size() - 1; j >= 0; j--) {
            if (nums[j] != sortNums[j]) {
                break;
            }
        }
        
        return j - i + 1;
    }
};

复杂度分析

时间复杂度：O(nlog(n)) 。排序消耗nlogn的时间。

空间复杂度：O(n) 。拷贝了一份原数组来进行排序。

2.2 不使用额外空间的用法

以{ 2, 6, 4, 8, 10, 9, 15 }为例，该数组中，最短无序数组是{6, 4, 8, 10, 9}，可以大概看出的规律是：区间的起点在原数组的第一个降序序列附近（6和4这里），区间的终点在从右到左第一个升序序列附近（10和9这里），因此这里可以认为无序子数组的起点和终点和整个数组的升降点相关。

那是不是说直接从第一个降序点和升序点取子数组就可以了呢？不行，以{ 3, 4, 6, 9, 2, 1 }为例，从左往右的第一个降序点是9和2，从右往左的升序点是1和2，但是失序的数组并不只是这三个元素{9, 2, 1}，而是{3, 4, 6, 9, 2, 1}。此时从左往右看，元素9左边大于1的数组序列也都属于失序数组元素；从右往左看，元素2右边所有比9小的也属于失序数组。

因此能通过以下算法即便能找出失序数组：

1. 从左往右找到第一个降序点，从这个点开始找到最大的元素max。
2. 从右往左找到第一个升序点，从这个点开始找到最小的元素min。
3. 从左往右遍历，第一个大于min的元素即是失序数组的起点。
4. 从右往左遍历，第一个小于max的元素即是失序数组的终点。

代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int max = INT_MIN;
        int min = INT_MAX;

        int i, j;

        // 从左往右，出现降序之后找最大值
        for (i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                min = min < nums[i] ? min : nums[i];
            }
        }
        
        // 从右往左，出现升序之后找最小值
        for (j = nums.size() - 1; j > 0; j--) {
            if (nums[j - 1] > nums[j] ) {
                max = max > nums[j - 1] ? max : nums[j - 1];
            }
        }
        
        // 从左往右找到第一个大于min的元素
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] > min)
                break;
        }
        
        // i遍历到最后一个元素，说明数组已经有序了
        if (i == nums.size())
            return 0;
        
        // 从右往左找到第一个小于max的元素
        for (j = nums.size() - 1; j >= 0; j--) {
            if (nums[j] < max)
                break;
        }
        // 计算区间大小
        return j - i + 1;
    }
};

算法复杂度

时间复杂度：O(n)。使用了4个O(n)的循环。

空间复杂度：O(1)。使用了常数空间。

来源：力扣（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))。