[TOC]

数据结构摘记(剑指Offer)

引言

NULL

题解

NULL

24 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

分析：

对于一棵树，要找到从根节点往下到叶节点所经过的节点的路径和为num，那么需要每次路过该节点时，加上该节点的值，离开该节点时将该节点的值减去。

例如：

从根节点进入，采用先序遍历的方式，先遍历根节点的左子树,并将该节点加入到路径，若路径和为num，则将该条路径保存，并继续遍历其左子树和右子树（假设左右子树存在0元素），若左右子树都遍历完，说明本条路径已经查到底了，将该条路径的尾元素pop出来，并将路径上的和sum减去该元素值。

例程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
  Solution(void) {}
  ~Solution(void) {}
  
  void addInput(const std::vector<std::string> &xs, int num) {
    head_ = deserializeTree(xs); // 构建树
    num_ = num;
  }
  
  std::vector<std::vector<int> > go(void) {
    return go(head_, num_);
  }
  
  std::vector<std::vector<int> > go(TreeNode *root, int expectNum) {
    paths_.clear();
    sum_ = 0;
    num_ = expectNum;
    std::vector<int> path;
    _preTraverse(root, path);
    return paths_;
  }
  
  void _preTraverse(TreeNode *node, std::vector<int> &path) {
    if(nullptr == node) return;
    sum_ += node->val;
    path.push_back(node->val);
    fprintf(stderr, "PUSH\t<< %d\t, sum: %d\n", node->val, sum_);
    if(sum_ == num_ and nullptr == node->left and nullptr == node->right) paths_.push_back(path);
    _preTraverse(node->left,  path);
    _preTraverse(node->right, path);
    sum_ -= node->val;
    path.pop_back();
    fprintf(stderr, "POP\t>> %d\t, sum: %d\n", node->val, sum_);
  }
protected:
  TreeNode *head_;
  int num_, sum_;
  std::vector<std::vector<int> > paths_;
};

25 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

分析

每一个节点都有其next指针和random指针，那么朴素的想法就是我用一个键值对map来存储第i个节点的next指针和random指针。先不考虑新链表的random指针，这样遍历一遍链表，就能够得到新链表第i个节点的next指针和random指针，分别在两个键值对里

对于新链表中的第i个节点，连接第i个节点->random = random_map[i]

例程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
struct RandomListNode {
  int label;
  struct RandomListNode *next, *random;
  RandomListNode(int x): label(x), next(nullptr), random(nullptr) {}
};
*/
class Solution {
public:
  RandomListNode *Clone(RandomListNode* pHead) {
    if(nullptr == pHead) return nullptr;
    int id = 0;
    RandomListNode *node = pHead;
    std::map<int, RandomListNode*> index_map, index_map_random; // 第i个节点的下一个节点指针，第i个节点的下一个随机节点指针
    RandomListNode *head = nullptr, *cur = nullptr;
    while(nullptr != node) {
      index_map[id] = new RandomListNode(node->label);
      index_map_random[id] = (nullptr == node->random? nullptr: new RandomListNode(node->random->label));
      if(head == nullptr) cur = head = index_map[id];
      else cur = cur->next = index_map[id];
      node = node->next;
      id++;
    }
    for(auto &m: index_map) m.second->random = index_map_random[m.first];
    return head;
  }
};

No Title

Description

分析

例程

1
2


No Title

Description

分析

例程

1
2