题目描述（简单难度）

226. Invert Binary Tree - 图1

反转二叉树，将二叉树所有的节点的左右两个孩子交换。

解法一 递归

对于二叉树的问题，用递归写的话就会异常简单了。交换左右节点，然后左右节点交给递归即可。

  1. public TreeNode invertTree(TreeNode root) {
  2.     if (root == null) {
  3.         return root;
  4.     }
  6.     TreeNode temp = root.left;
  7.     root.left = root.right;
  8.     root.right = temp;
  10.     invertTree(root.left);
  11.     invertTree(root.right);
  12.     return root;
  13. }

解法二 DFS 栈

当然递归都可以用栈模拟，因为解法一的递归比较简单，所以改写也比较容易。

  1. public TreeNode invertTree(TreeNode root) {
  2.     Stack<TreeNode> stack = new Stack<>();
  3.     stack.push(root);
  4.     while (!stack.isEmpty()) {
  5.         TreeNode cur = stack.pop();
  6.         if (cur == null) {
  7.             continue;
  8.         }
  9.         TreeNode temp = cur.left;
  10.         cur.left = cur.right;
  11.         cur.right = temp;
  13.         stack.push(cur.right);
  14.         stack.push(cur.left);
  15.     }
  16.     return root;
  17. }

解法三 BFS 队列

既然可以 DFS，那么也可以 BFS，只需要将解法二的栈改成队列即可。代码不用怎么变，但二叉树的遍历顺序完全改变了。

  1. public TreeNode invertTree(TreeNode root) {
  2.     Queue<TreeNode> queue = new LinkedList<>();
  3.     queue.offer(root);
  4.     while (!queue.isEmpty()) {
  5.         TreeNode cur = queue.poll();
  6.         if (cur == null) {
  7.             continue;
  8.         }
  9.         TreeNode temp = cur.left;
  10.         cur.left = cur.right;
  11.         cur.right = temp;
  13.         queue.offer(cur.left);
  14.         queue.offer(cur.right);
  15.     }
  16.     return root;
  17. }

总

一道比较简单的题，用递归很快就可以解决。之前一直认为，递归改写成解法二或者解法三的迭代那样会更好一些，因为可以防止递归的堆栈溢出。虽然也有缺点，那就是代码会相对更复杂些，可读性有些降低。

刚才看到 王垠 大神的一个不一样的观点，分享一下。

226. Invert Binary Tree - 图2

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情