1 题目
Invert a binary tree.
4
/
2 7
/ /
1 3 6 9
to
4
/
7 2
/ /
9 6 3 1
接口: public TreeNode invertTree(TreeNode root)
2 思路
反转一颗二叉树。
可以用递归和非递归两种方法来解。
- 递归的方法，写法非常简洁，五行代码搞定，交换当前左右节点，并直接调用递归即可。
- 非递归的方法，参考树的层序遍历，借助
Queue来辅助，先把根节点排入队列中，然后从队中取出来，交换其左右节点，如果存在则分别将左右节点在排入队列中，以此类推直到队列中木有节点了停止循环，返回root即可。
复杂度:两种方法的时间和空间复杂度一样，Time O(n)；Space O(n)
3 代码
- 思路1：
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
TreeNode tmp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(tmp);
return root;
}
4 总结
考察二叉树的遍历。
非递归的实现，复习。请实现非递归。