每日题解:LeetCode 1008. 先序遍历构造二叉树

Author Avatar
清水雅然君 08月 19,2020

题目地址

题目描述

返回与给定先序遍历 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;
    }
};

解题思路

递归

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

{
if(条件体){
//结束判断
return null;
}
if(条件体){
//返回值
return 返回值;
}
1、赋值
2、返回结果
}

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

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

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

//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;

再完善递归的结束判断和赋值,采用分治的思路,
在这里插入图片描述
如果不看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;
    }