Java实现给定一棵二叉树,使用递归的方法实现二叉树的左右子树交换,并输出交换后的二叉树的先序遍历结果。
时间: 2023-12-01 10:23:10 浏览: 92
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
可以通过以下步骤实现:
1. 定义一个节点类,包含一个值和左右子节点指针的引用。
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
```
2. 创建一个递归函数,用于交换二叉树的左右子树。
```java
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
```
3. 创建一个函数,接收一个二叉树的根节点,返回先序遍历的结果。
```java
public String preorderTraversal(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
return "";
}
sb.append(root.val);
sb.append(preorderTraversal(root.left));
sb.append(preorderTraversal(root.right));
return sb.toString();
}
```
4. 测试函数。
```java
public static void main(String[] args) {
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);
Solution solution = new Solution();
TreeNode inverted = solution.invertTree(root);
String preorder = solution.preorderTraversal(inverted);
System.out.println(preorder); // "4 7 9 6 2 3 1"
}
```
这样就可以通过递归的方法交换二叉树的左右子树,并输出交换后的二叉树的先序遍历结果了。
阅读全文