一、题目
翻转一棵二叉树。
示例
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
二、递归解法
1. 解题思路
图解：
递归节点处理过程
其实就是交换一下左右节点，然后再递归的交换左节点，右节点
根据动画图我们可以总结出递归的两个条件如下：
- 终止条件：当前节点为 null 时返回
- 交换当前节点的左右节点，再递归的交换当前节点的左节点，递归的交换当前节点的右节点
2. 编码
由上分析可知为二叉树的前序遍历递归过程，先回忆一遍二叉树前序遍历的代码模版。
二叉树前序遍历递归代码模版：
/**
* 先序遍历递归 根 左子 右子
*/
fun preOrderTraverse(root: BTreeNode?) {
if (root == null) {
return
}
print("${root.value} ")
preOrderTraverse(root.left)
preOrderTraverse(root.right)
}
我们只需在打印节点value的地方做节点的左右孩子交换处理就可以。
示例代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
3. 时空复杂度分析
时间复杂度：每个元素都必须访问一次，所以是 O(n)
空间复杂度：最坏的情况下，需要存放 O(h) 个函数调用(h是树的高度)，所以是 O(h)
三、迭代解法
1. 解题思路
使用层次遍历每个节点，交换每个节点的左右孩子节点
图解：
层次遍历节点处理过程
2. 编码
先回忆层次遍历的代码模版，只需在打印节点的value的地方对节点左右孩子交换处理即可。
层次遍历的代码模版：
val queue = LinkedList<BTreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
val node = queue.poll()
print("${node?.value} ")
if (node?.left != null) queue.addLast(node.left)
if (node?.right != null) queue.addLast(node.right)
}
此题示例代码：
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun invertTree(root: TreeNode?): TreeNode? {
if(root == null){
return null;
}
val queue = LinkedList<TreeNode?>()
queue.addLast(root)
while(queue.isNotEmpty()){
val node = queue.poll()
val temp = node?.left
node?.left = node?.right
node?.right = temp
if(node?.left != null) queue.addLast(node?.left)
if(node?.right != null) queue.addLast(node?.right)
}
return root
}
}
3. 时空复杂度分析
时间复杂度：每个节点都需要入队列、出队列一次，所以是 O(n)
空间复杂度：最坏的情况下会包含所有的叶子节点，完全二叉树叶子节点是 n/2个，所以空间复杂度是 0(n)
四、总结
- 此题难度为easy
- 熟记前序遍历、层次遍历步骤和代码模版将很快解题
leetcode传送门：226. 翻转二叉树
