编写递归算法,将二叉树中所有结点的左、右子树相互交换。
时间: 2023-06-01 19:01:43 浏览: 352
用递归算法把所有结点的左右子树互相交换
### 回答1:
递归算法如下:
1. 如果当前节点为空,返回空。
2. 交换当前节点的左右子树。
3. 递归交换当前节点的左子树。
4. 递归交换当前节点的右子树。
代码实现如下:
```
void swapTree(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
swapTree(root->left);
swapTree(root->right);
}
```
### 回答2:
将二叉树中所有节点的左、右子树相互交换,可以使用递归算法来实现。
首先,我们需要先判断当前节点是否为空节点,如果是则直接返回。如果不是空节点,就交换它的左右子树。接着,我们递归地分别对左右子树进行相同的操作,直到将整个二叉树的节点都交换完。
具体实现如下:
```
void invertTree(TreeNode* root) {
if(root == nullptr) { // 如果当前节点为空,直接返回
return;
}
swap(root->left, root->right); // 交换当前节点的左右子树
invertTree(root->left); // 递归处理左子树
invertTree(root->right); // 递归处理右子树
}
```
在这里,我们采用了C++的指针操作,使用swap函数来交换当前节点的左右子树。然后分别递归处理左右子树,直到完全交换完整棵树。
值得注意的是,这里并没有返回值,而是对原树进行修改。
总之,递归算法可以帮助我们快速简洁地完成二叉树节点的交换操作,而且可以处理多种情况,非常灵活。
### 回答3:
二叉树中所有结点的左、右子树交换操作可以通过递归算法来实现。具体思路如下:
1.定义一个递归函数swapTree(TreeNode root)。
2.首先判断节点root是否为空,如果为空则直接返回null。
3.递归交换root节点的左右子树,即swapTree(root.left)和swapTree(root.right)。
4.然后将root节点的左右子树进行交换,即将root.left赋值给一个新的TreeNode tmp,然后将root.right赋值给root.left,最后将tmp赋值给root.right。
5.最后返回交换后的root节点。
代码实现如下:
public TreeNode swapTree(TreeNode root) {
if (root == null) {
return null;
}
swapTree(root.left);
swapTree(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
该算法的时间复杂度为O(n),其中n为二叉树中节点的个数,因为每个节点只会被访问一次。该算法的空间复杂度为O(h),其中h为二叉树的高度,因为递归过程中需要消耗堆栈空间。
阅读全文