LeetCode第1008题,难度中等,题目序号都在各种500开外乱飘。
原题地址:https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/
题目描述:
返回与给定先序遍历 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]
提示:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
由于是先序遍历,所以就没有使用递归的方式。
首先将遍历的第一个节点作为根节点(这里需要回顾确认下先序遍历的意义)。然后开始遍历之后的每一个节点,由于该树是二叉搜索树,所以每个节点,都去从根节点开始往下遍历,找到NULL节点,将该节点设置为当前遍历到的节点,退出当前的遍历循环,继续下一个节点的遍历。
直到所有的节点都遍历结束之后,其实效率不高,因为每遍历一个节点,都需要从根节点开始遍历一次数组,进行一次搜索查询。但是实在没想到什么更好的办法
中文官网题解:
https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal/solution/
个人题解:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
TreeNode root = new TreeNode(preorder[0]);
for (int i = 1; i < preorder.length; i++) {
TreeNode node = root;
while (true) {
if (preorder[i] < node.val) {
if (node.left == null) {
node.left = new TreeNode(preorder[i]);
break;
} else {
node = node.left;
}
} else {
if (node.right == null) {
node.right = new TreeNode(preorder[i]);
break;
} else {
node = node.right;
}
}
}
}
return root;
}
}
结果:
可能是人太少,所以还是100%吧,感觉已经很多次100%了,但是都是简单级别的啊。