前序遍历 - 图1 前序遍历作为二叉搜索树的一个遍历方式，其遍历顺序是: 根节点->左子树->右子树。关于前序遍历的各种算法也是多种多样。接下来，我就在这篇文章中陆续把前序遍历的相关力扣例题去列举出来。

力扣1008 先序遍历构造二叉树

1008. 先序遍历构造二叉树

返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

示例：

输入：[8,5,1,7,10,12]

输出：[8,5,10,1,7,null,12]

提示：

1 <= preorder.length <= 100

先序 preorder 中的值是不同的。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题利用了二叉搜索树的特点，即根节点的值大于其左子树的值，小于其右子树的值。在前序遍历的链表中，根据前序遍历的顺序 根节点->左子树->右子树 因此链表的第一项一定是根节点。那么链表中小于根节点的部分就是其根节点的左子树，大于根节点的部分就是根节点的右子树。按照这个思路，便有如下的解法。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     TreeNode* bstFromPreorder(vector<int>& preorder) {
  15.         if(preorder.size() == 0)
  16.             return NULL;
  17.         if(preorder.size() == 1)
  18.             return new TreeNode(preorder[0]);
  20.         TreeNode *root = new TreeNode(preorder[0]);
  22.         int leftindex = 1;
  24.         for(; leftindex < preorder.size(); leftindex++)
  25.         {
  26.             if(preorder[leftindex] > preorder[0])
  27.                 break;
  28.         }
  30.         vector<int>left(preorder.begin() + 1, preorder.begin() + leftindex);
  31.         root->left = bstFromPreorder(left);
  32.         vector<int>right(preorder.begin() + leftindex, preorder.end());
  33.         root->right = bstFromPreorder(right);
  35.         return root;
  36.     }
  37. };

力扣889 根据前序和后序遍历构造二叉树

889. 根据前序和后序遍历构造二叉树

返回与给定的前序和后序遍历匹配的任何二叉树。

pre 和 post 遍历中的值是不同的正整数。

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

输出：[1,2,3,4,5,6,7]

提示：

1 <= pre.length == post.length <= 30

pre[] 和 post[] 都是 1, 2, …, pre.length 的排列

每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题和上道题所不同的地方在于，这道题的二叉树不是二叉搜索树，因此无法利用二叉搜索树的性质。因此这道题给了两个遍历序列，前序遍历和后序遍历，前序遍历我们在之前已经说过了，那么后序遍历的顺序是什么呢？后序遍历的顺序是：左子树->右子树->根节点。回到这道题上，我们便可以根据前序遍历和中序遍历的特点来构造出二叉树。对于这道题我们依旧采用递归的方法来做，那么对于递归这种解法，就需要从前序遍历和后序遍历中找出这三个部分。根节点，根节点的左子树部分和根节点的右子树部分。那么根据前序遍历的特点，第一个数就是根节点，同时后序遍历的最后一个数也是根节点。而前序遍历的第二个数就是其左子树的第一个点，而在后序遍历中，这个点恰好是根节点左子树部分的最后一个点，那么通过这个点，我们就可以在后序遍历中找到左子树部分到底有多少个点，然后便可以以此来将前序遍历和后序遍历的分成根节点，左子树和右子树三个部分进行递归的计算。下面是这道题的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        if(pre.size() == 0 || post.size() == 0)
            return NULL;
        if(pre.size() == 1)
            return new TreeNode(pre[0]);
        if(post.size() == 1)
            return new TreeNode(post[0]);

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

        int leftendindex = 1;
        int leftendvalue = pre[leftendindex];

        for(int i = 0; i < post.size(); i++)
        {
            if(post[i] == leftendvalue)
                break;
            leftendindex++;
        }

        vector<int>leftpreorder(pre.begin() + 1, pre.begin() + 1 + leftendindex);
        vector<int>leftpostorder(post.begin(), post.begin() + leftendindex);
        vector<int>rightpreorder(pre.begin() + 1 + leftendindex, pre.end());
        vector<int>rightpostorder(post.begin() + leftendindex, post.end()- 1);

        root->left = constructFromPrePost(leftpreorder, leftpostorder);
        root->right = constructFromPrePost(rightpreorder, rightpostorder);

        return root;
    }
};

力扣1382 将二叉搜索树变平衡

1382. 将二叉搜索树变平衡

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

如果有多种构造方法，请你返回任意一种。

示例：

输入：root = [1,null,2,null,3,null,4,null,null]

输出：[2,1,3,null,null,null,4]

解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示：

树节点的数目在 1 到 10^4 之间。

树节点的值互不相同，且在 1 到 10^5 之间。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/balance-a-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先得到有序列表，然后根据有序列表去构建平衡搜索树。这里需要注意的是对于边界的处理。

/**
 * 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:
    vector<int> inorderSeq;

    void getInorder(TreeNode *node)
    {
        if(node == nullptr)
            return;

        getInorder(node->left);
        inorderSeq.push_back(node->val);
        getInorder(node->right);
        return;
    }

    TreeNode * build(int l, int r)
    {
        if(l > r)
            return nullptr;

        int mid = (r + l) / 2;
        TreeNode *root = new TreeNode(inorderSeq[mid]);
        root->left = build(l, mid - 1);
        root->right = build(mid + 1, r);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        getInorder(root);
        return build(0, inorderSeq.size() - 1);
    }
};