根据二叉搜索树前序遍历的数组可以构建唯一的二叉树吗,如果可以的话,用java代码实现
时间: 2024-09-29 08:05:11 浏览: 33
[力扣]144. 二叉树的前序遍历java
5星 · 资源好评率100%
可以的,给定一个整数序列,通过前序遍历的方式(根节点 -> 左子树 -> 右子树),我们可以唯一确定一棵二叉搜索树(BST)。这是因为二叉搜索树的性质决定了节点的顺序:左子树所有元素小于根节点,右子树所有元素大于根节点。
以下是使用 Java 实现的一个示例:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean isValidSerialization(String preorder) {
if (preorder.isEmpty()) return true;
String[] nodes = preorder.split(",");
if (nodes.length == 0 || nodes[0].equals("#")) return false;
Stack<TreeNode> stack = new Stack<>();
for (String node : nodes) {
if (!node.equals("#")) {
// 插入新节点
TreeNode newNode = new TreeNode(Integer.parseInt(node));
if (stack.isEmpty() || newNode.val > stack.peek().val) {
// 如果栈为空或新节点值大于栈顶节点,则插入到顶部
stack.push(newNode);
} else {
// 否则将大于栈顶节点的节点一直推到栈顶,并与当前节点连接
while (!stack.isEmpty() && newNode.val <= stack.peek().val) {
TreeNode temp = stack.pop();
newNode.left = temp;
}
stack.push(newNode);
}
} else {
// 遇到空节点表示结束,检查栈是否为空
if (!stack.isEmpty()) return false;
}
}
return stack.isEmpty(); // 遍历结束后,栈为空说明可以构成唯一二叉搜索树
}
```
这个 `isValidSerialization` 函数接受一个字符串,表示前序遍历的结果,它会判断该序列是否能形成一个有效的二叉搜索树的前序遍历。如果能够形成,返回 `true`,否则返回 `false`。
阅读全文