每日题解: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;
    }
};

解题思路

递归

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

{
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;
    }
最近的文章

每日题解:LeetCode 241. 为运算表达式设计优先级

题目地址题目描述定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含+,-以及*。示例1:输入:"2-1-1"输出:[0,2]解释:((2-1)-1)=0(2-(1-1))=2示例2:输入:&quo…

继续阅读
更早的文章

每日题解:LeetCode 109. 有序链表转换二叉搜索树

题目地址题目描述给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例:给定的有序链表:[-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这…

继续阅读