1. 重建二叉树

给出二叉树的前序遍历和中序遍历，重建二叉树。树是通过递归定义的，所以这题重建也是使用递归去重建。
先顺序遍历的首元素就是二叉树的根节点。再去中序遍历中去找这个元素，即可分出左子树和右子树。遍历先序遍历，1.树的根节点、2.左子树根节点、3.右子树根节点。对于树的左、右子树，仍可使用以上步骤划分子树的左右子树。
因为中序遍历和前序遍历元素个数肯定一致，所以可以通过中序遍历去确定前序遍历中左子树和右子树的分界线。截屏2020-10-29 20.48.10.png

  1. class Solution {
  2. private:
  3.     unordered_map<int, int> index;
  4. public:
  5.     TreeNode *
  6.     myBuildTree(const vector<int> &preorder, const vector<int> &inorder, int preorder_left, int preorder_right,
  7.                 int inorder_left, int inorder_right) {
  8.         if (preorder_left > preorder_right) {
  9.             return nullptr;
  10.         }
  11.         int preorder_root = preorder_left;
  12.         int inorder_root = index[preorder[preorder_root]];
  13.         TreeNode *root = new TreeNode(preorder[preorder_root]);
  14.         int size_left_subtree = inorder_root - inorder_left;
  15.         root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left,
  16.                                  inorder_root - 1);
  17.         root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right,
  18.                                   inorder_root + 1, inorder_right);
  19.         return root;
  20.     }
  21.     TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
  22.         int n = preorder.size();
  23.         for (int i = 0; i < n; ++i) {
  24.             index[inorder[i]] = i;
  25.         }
  26.         return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
  27.     }
  28. };
  29. //前序遍历 preorder = [3,9,20,15,7]
  30. //中序遍历 inorder = [9,3,15,20,7]

2. 数值的整数次方

暴力法用for坐下来时间复杂度有n，分治法可以降为log2n，思路也很简单，递归和分治，比如第五章 分治法 - 图2。奇数只需要用取余%2即可。

  1. class Solution {
  2. public:
  3.     double myPow(double x, int n) {
  4.         if (n == 0) 
  5.             return 1;
  6.         if (n == 1) 
  7.             return x;
  8.         if (n == -1) 
  9.             return 1 / x;
  10.         double half = myPow(x, n / 2);
  11.         double rest = myPow(x, n % 2);
  12.         return rest * half * half;
  13.     }
  14. };

3. 二叉搜索树的后序遍历序列

递归+分治。利用二叉搜索树的性质，设置一个pointer遍历vector，找到左子树和右子树的划分点，递归下去继续。

  1. class Solution{
  2. public:
  3.     bool verifyPostorder(vector<int>& postorder){
  4.         return recur(postorder, 0, postorder.size() - 1);     
  5.     }
  6. private:
  7.     bool recur(vector<int> &postorder, int i,int j){
  8.         //设置递归结束条件
  9.         if (i>=j)
  10.             return true;
  11.         int point = i;
  12.         //遍历
  13.         while (postorder[point]<postorder[j])
  14.             point++;
  15.         int m = point;
  16.         while (postorder[point]>postorder[j])
  17.             point++;
  18.         return point==j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
  19.     }
  20. };