交换二叉树中每个结点的左孩子和右孩子的算法
时间: 2023-06-23 10:10:24 浏览: 54
这个问题可以用递归和迭代两种方法来解决。
递归方法:
对于当前节点,交换其左右子树,并分别递归地交换左右子树的子节点。
具体实现代码如下:
```python
def invertTree(root):
if not root:
return None
root.left, root.right = root.right, root.left
invertTree(root.left)
invertTree(root.right)
return root
```
迭代方法:
使用一个栈来保存待交换的节点,然后依次取出节点,交换其左右子树,将左右子树入栈。
具体实现代码如下:
```python
def invertTree(root):
if not root:
return None
stack = []
stack.append(root)
while stack:
node = stack.pop()
node.left, node.right = node.right, node.left
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return root
```
以上两种方法的时间复杂度均为 $O(n)$,其中 $n$ 为二叉树的节点数。