剑指Offer刷题（二十四）：二叉树中和为某一值的路径

题目

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

深度优先搜索.使用前序遍历,使用两个全局变量result和tmp,result来存放最终结果,tmp来存放临时结果

每次遍历,我们先把root的值压入tmp，然后判断当前root是否同时满足:

与给定数值相减为0
左子树为空

右子树为空
如果满足条件,就将tmp 压入result中,否则,依次遍历左右子树.需注意的是,遍历左子树的时候,全局变量tmp是不清空的.直到到了根节点才清空tmp

C++

class Solution{
public:
    vector<vector<int>> Findpath(TreeNode * root,int expectNumber){
    if(root==NULL){
        return result;
    }
    tmp.push_back(root->val);
    if((expectNumber-root->val)==0&&root->left==NULL&&right==NULL){
        result.push_back(tmp);
    }

    Findpath(root->left,expectNumber-root->val);
    Findpath(root->right,expectNumber-root->val);

    tmp.pop_back();
    return result;
    }
private:
    vector<vector<int>> result;
    vector<int> tmp;
};

剑指Offer刷题（二十五）：复杂链表的复制

题目

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

思路

一开始,没太看懂这题,画个图就大致能明白了.由于输出结果中不能返回参数中的节点引用,所以复制的节点的地址是全新的.next指针可以顺序的将这些点连接起来,而random由于随机连接节点它只能知道它所连的节点的值,但题中没说不能重复值出现,所以并不知道它连接的节点的顺序编号是几.

方法有许多,1. 比如先将链表顺序连接好再查找各个节点的random里存的是第几个对应节点.显然这里查找比较费时,时间复杂度会是$O(n^2)$.2.另一种方法是复制label和next的同时建立一个hash来存放就节点和新节点的对应关系,这是用空间来换时间.

网上完美的方法:
不用新创建hash来存储新节点与旧节点的对应关系,直接将新节点建立在对应旧节点的后面.根据这种连接的天然的奇偶关系来表示新旧节点的对应关系.
具体如下图:

C++

#include<iostream>
using namespace std;

struct RandomListNode {
    int label;
    struct RandomListNode * next, * random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
class Solution{
public:
    void CloneNodes(RandomListNode * pHead){
        RandomListNode* pNode=pHead;
        while(pNode!=NULL){
            RandomListNode * pCloned=new RandomListNode(0);
            pCloned->label=pNode->label;
            pCloned->next=pNode->next;
            pCloned->random=NULL;

            pNode->next=pCloned;
            pNode=pCloned->next;
        }
    }

    void ConnectSiblingNodes(RandomListNode* pHead){
        RandomListNode* pNode=pHead;
        while(pNode!=NULL){
            RandomListNode* pCloned=pNode->next;
            if(pNode->random!=NULL){
                pCloned->random=pNode->random->next;
            }
            pNode=pCloned->next;
        }
    }

    RandomListNode * ReconnectNodes(RandomListNode * pHead){
        RandomListNode* pNode=pHead;
        RandomListNode* pClonedHead=NULL;
        RandomListNode* pClonedNode=NULL;

        if(pNode!=NULL){
            pClonedHead=pClonedNode=pNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
        }
        while(pNode!=NULL){
            pClonedNode->next=pNode->next;
            pClonedNode=pClonedNode->next;
            pNode->next=pClonedNode->next;
            pNode=pNode->next;
        }
        return pClonedHead;
    }

    RandomListNode* Clone(RandomListNode *pHead){
        CloneNodes(pHead);
        ConnectSiblingNodes(pHead);
        return ReconnectNodes(pHead);
    }

};