利用括号表示串创建二叉树,并通过二叉树的中序遍历结果进行验证。java
时间: 2024-01-23 12:16:16 浏览: 18
可以按照以下步骤实现:
1. 定义一个二叉树节点类,包含左右子节点和节点值:
```
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char x) { val = x; }
}
```
2. 创建一个栈来辅助构建二叉树,遇到左括号就创建新节点,遇到右括号就弹出栈顶节点:
```
public static TreeNode createTree(String s) {
if (s == null || s.length() == 0) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode root = null;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
TreeNode node = new TreeNode(s.charAt(i + 1));
if (root == null) {
root = node;
}
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.push(node);
i++;
} else if (c == ')') {
stack.pop();
}
}
return root;
}
```
3. 对二叉树进行中序遍历,将节点值按顺序拼接成字符串:
```
public static String inorderTraversal(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
sb.append(curr.val);
curr = curr.right;
}
return sb.toString();
}
```
4. 测试代码:
```
public static void main(String[] args) {
String s = "(A(B(D)(E))(C(F)(G)))";
TreeNode root = createTree(s);
String result = inorderTraversal(root);
System.out.println(result.equals("DEBAFCG"));
}
```
运行结果为 true,说明二叉树创建成功并且中序遍历结果正确。