给定一棵二叉树,使用递归的方法实现二叉树的左右子树交换,并输出交换后的二叉树的先(前)序遍历结果。
时间: 2023-05-31 16:20:05 浏览: 163
### 回答1:
可以使用递归的方法实现二叉树的左右子树交换,具体步骤如下:
1. 如果当前节点为空,直接返回。
2. 交换当前节点的左右子树。
3. 递归交换当前节点的左子树。
4. 递归交换当前节点的右子树。
交换后的二叉树的先(前)序遍历结果可以通过遍历交换后的二叉树来获取。
具体代码如下:
```python
class TreeNode:
def __init__(self, val=, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
return root
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
# 测试代码
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(preorderTraversal(root)) # [4, 2, 1, 3, 7, 6, 9]
invertTree(root)
print(preorderTraversal(root)) # [4, 7, 9, 6, 2, 3, 1]
```
输出结果为:
```
[4, 2, 1, 3, 7, 6, 9]
[4, 7, 9, 6, 2, 3, 1]
```
可以看到,交换后的二叉树的先(前)序遍历结果为 `[4, 7, 9, 6, 2, 3, 1]`。
### 回答2:
二叉树的左右子树交换,是在每个节点上都需要进行的操作。我们可以使用递归的方法实现这个操作,即从根节点开始,递归地交换每个节点的左右子树。
实现起来很简单,只需遵循以下几个步骤:
1.判断当前节点是否为空,若为空则直接返回。
2.交换当前节点的左右子树。
3.递归地交换当前节点的左右子树。
完成以上步骤之后,我们就可以顺便输出先(前)序遍历结果了。先序遍历的顺序是:根节点 -> 左子树 -> 右子树。因此,在递归交换子树的同时,我们可以输出当前节点的值,即可完成先序遍历。
具体代码实现如下:
```
void swapTree(TreeNode* root) {
if (root == nullptr) {
return;
}
TreeNode* tmp = root->left;
root->left = root->right;
root->right = tmp;
cout << root->val << " "; //输出先序遍历结果
swapTree(root->left);
swapTree(root->right);
}
```
至此,我们已经成功地实现了二叉树的左右子树交换,并输出了交换后的先序遍历结果。
### 回答3:
首先,定义一个二叉树节点的结构体,存储节点的值和左右子节点指针。
然后,定义一个递归函数,传入一个二叉树节点指针作为参数。在函数内部,交换节点的左右子树,再递归调用函数分别交换左子树和右子树。
最后,以先序遍历方式遍历交换后的二叉树并输出节点值,即可得到交换后的结果。
具体的代码实现如下:
```c++
// 定义二叉树节点结构体
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void swapTree(TreeNode* root) {
if (!root) {
return;
}
// 交换左右子树
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
// 递归交换左右子树
swapTree(root->left);
swapTree(root->right);
}
void preorderTraversal(TreeNode* root) {
if (!root) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
int main() {
// 构造测试用例
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
// 交换左右子树并输出结果
swapTree(root);
preorderTraversal(root);
return 0;
}
```
以上便是递归实现二叉树左右子树交换的代码。需要说明的是,在交换左右子树的时候,要先保存原来的左子树,否则交换后就丢失了原来的左子树。此外,我们还需注意二叉树的遍历方式,题目要求输出先序遍历结果,因此我们使用了先序遍历的方式输出交换后的节点值。
阅读全文