每日题解:LeetCode 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]

解法

class Solution {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        int len;
        if ((len= preorder.size())==0) {
            return nullptr;
        }
        return buildBST(preorder, 0, len - 1);
    }

    TreeNode* buildBST(vector<int>& preorder,int left,int right) {
        if (left > right) {
            return nullptr;
        }

        TreeNode* root = new TreeNode(preorder[left]);
        if (left == right) {
            return root;
        }

        int i = left;
        while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
            i++;
        }

        TreeNode* leftTree = buildBST(preorder, left + 1, i);
        TreeNode* rightTree = buildBST(preorder, i + 1, right);
        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

解题思路

递归

涉及到二叉树先考虑递归再说，递归大致结构体

{
if(条件体){
//结束判断
return null;
}
if(条件体){
//返回值
return 返回值;
}
1、赋值
2、返回结果
}
1
2
3
4
5
6
7
8
9
10
11
12

然后分析题目的例子，前序遍历构建二叉搜索树
1、二叉搜索树的特点，左小右大
2、前序遍历的特点，第一个数就是根节点
根据以上的特点，我们可以将前序遍历分成两个部分或者说三个部分
1、根节点|左子树|右子树，其中root>左子树的值，root<右子树的值

//找到右子树的节点
  int i = left;
        while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
            i++;
}
1
2
3
4
5

找到右子树的节点后，就可以递归构建左右子树

//left就是根节点，left+1就是左子树的节点
 TreeNode* leftTree = buildBST(preorder, left + 1, i);
        TreeNode* rightTree = buildBST(preorder, i + 1, right);
        root->left = leftTree;
        root->right = rightTree;
        return root;
1
2
3
4
5
6

再完善递归的结束判断和赋值，采用分治的思路，

如果不看8的根节点，5节点是1和7的根节点；10是12的根节点，依次类推，每个节点都是“根节点”

  TreeNode* buildBST(vector<int>& preorder,int left,int right) {
        if (left > right) {
            return nullptr;
        }

        TreeNode* root = new TreeNode(preorder[left]);
        //左右指针相等时，则是根节点，返回结果
        if (left == right) {
            return root;
        }
        int i = left;
        while (i + 1 <= right && preorder[i + 1] < preorder[left]) {
            i++;
        }

        TreeNode* leftTree = buildBST(preorder, left + 1, i);
        TreeNode* rightTree = buildBST(preorder, i + 1, right);
        root->left = leftTree;
        root->right = rightTree;
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21