剑指offer第三题：从头到尾打印链表，比较简单。代码如下：

#include <vector>
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        if(head == nullptr) return vector<int>();

        vector<int> r;
        while (head != nullptr) {
            r.push_back(head->val);
            head = head->next;
        }
        reverse(r.begin(), r.end());
        return r;
    }
};

重建二叉树：比较难的题目。
题目

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

参考博客：剑指 Offer 07. 重建二叉树 – leetcode 剑指offer系列 – 知乎
思想1：递归。
前序遍历是根左右，中序遍历是左根右。
前序遍历可以得到根节点，拿根节点去对应中序遍历，可以知道中序遍历序列中根节点左边的是根的左子树，右边的是根的右子树。如：

pre: 1 2 3 4 5 6 7
tin: 3 2 4 1 6 5 7
说明1的左边肯定是324,右边肯定是657

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    int n = pre.size();
    int m = vin.size();
    if(n == 0 || m == 0) 
        return nullptr;

    TreeNode *root = new TreeNode(pre[0]); 
    int root_val = pre[0];

    for(int i = 0; i < vin.size(); i++){
        //找到中序遍历中的前序第一个元素
        if(root_val == vin[i]){ 
            //左子树的前序遍历
            vector<int> leftpre(pre.begin() + 1, pre.begin() + i + 1); 
            //左子树的中序遍历
            vector<int> leftvin(vin.begin(), vin.begin() + i); 
            //构建左子树
            root->left = reConstructBinaryTree(leftpre, leftvin); 
            //右子树的前序遍历
            vector<int> rightpre(pre.begin() + i + 1, pre.end()); 
            //右子树的中序遍历
            vector<int> rightvin(vin.begin() + i + 1, vin.end()); 
            //构建右子树
            root->right = reConstructBinaryTree(rightpre, rightvin); 
            break;
        }
    }
    return root;
}

这种算法的时空复杂度都是O(n)。

另一种方法是栈，时空复杂度一样都是O(n)。 思路是基于前序遍历的性质：根左右。某个点p的下一个节点q，只有下面3种情况：
1. q是p的左节点
2. q是p的右节点(p没有左节点)
3. q是p的祖先节点的右节点
其中2，3情况可以归结为：q是某子树的右节点。

具体例子：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

判断3之后的9究竟是哪一种情况，要结合中序遍历，中序遍历第一个数字是9而不是3，说明9肯定是在3的左侧(中序遍历左根右)。20呢，根据中序遍历，20不可能是9的左节点，只可能是3的右子树节点。

1. 遍历前序序列, 使用栈保存当前前序已经遍历的节点
2. 然后使用一个下标记录当前中序节点位置
3. 最后根据栈顶节点和当前中序节点的值是否相等来判断节点关系
   1. 不相等: 表示当前节点一定是栈顶节点的左子节点
   2. 相等（如果栈顶节点值 = 当前中序节点值，说明栈顶节点的左子树已处理完毕）: 则需要弹出栈并向后移中序下标, 直到值不相等或者栈为空位置, 记录最后一个值相等的节点, 其右子节点就是当前节点了

代码如下

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        if(n == 0 || m == 0) 
            return NULL;
        stack<TreeNode*> s;
        
        //首先建立前序根节点
        TreeNode *root = new TreeNode(pre[0]); 
        TreeNode *cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //前序序列的值和中序序列的值不一样
            if(cur->val != vin[j]){ 
                cur->left = new TreeNode(pre[i]);
                //入栈
                s.push(cur);
                cur = cur->left; 
            }else{// 值相等，说明栈顶节点的左子树已处理完毕
                j++;
                //弹出到符合的祖先
                while(!s.empty() && s.top()->val == vin[j]){ 
                    cur = s.top();
                    s.pop();
                    j++;
                }
                //添加右节点
                cur->right = new TreeNode(pre[i]); 
                cur = cur->right;
            }
        }
        return root;
    }
};