学习目标：

分治算法

学习内容：

剑指 Offer 07. 重建二叉树

分治

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    this->preorder = preorder;
    for (int i = 0; i < inorder.size(); i++)
      dic[inorder[i]] = i;
    return recur(0, 0, inorder.size() - 1);
  }

private:
  vector<int> preorder;
  unordered_map<int, int> dic;

  TreeNode *recur(int root, int left, int right) {
    if (left > right)
      return NULL;
    TreeNode *node = new TreeNode(preorder[root]);
    int i = dic[preorder[root]];
    node->left = recur(root + 1, left, i - 1);
    node->right = recur(root + i - left + 1, i + 1, right);
    return node;
  }
};

剑指 Offer 16. 数值的整数次方

使用 INT_MIN 减内存但耗时

class Solution {
public:
  double myPow(double x, int n) {
    if (x == 0.0)
      return x;
    if (n == 0)
      return 1;
    if (n == 1)
      return x;
    if (n > 0) {
      if (n % 2 == 0)
        return myPow(x * x, n / 2);
      else
        return x * myPow(x * x, n / 2);
    } else {
      if (n == -2147483648) {
        int b = n / 2; 
        b = -b;
        return myPow((1 / x) * (1 / x), b);
      } else
        return myPow(1 / x, -n);
    }
  }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

骄傲，虽然内存和时间都占用太高。

class Solution {
public:
  bool verifyPostorder(vector<int> &postorder) {
    if (postorder.empty())
      return true;
    vector<int> left, right;
    int n = postorder.size();
    int i;
    for (i = 0; i < n - 1; ++i) {
      if (postorder[i] < postorder[n - 1])
        left.push_back(postorder[i]);
      else
        break;
    }
    for (int j = i; j < n - 1; ++j) {
      if (postorder[j] > postorder[n - 1])
        right.push_back(postorder[j]);
      else
        return false;
    }
    return verifyPostorder(left) && verifyPostorder(right);
  }
};

今天就过年咯。 田田新年快乐，永远18.哈哈哈