Invert Binary Tree

描述

Invert a binary tree.

  1.      4
  2.    /   \
  3.   2     7
  4.  / \   / \
  5. 1   3 6   9

to

  1.      4
  2.    /   \
  3.   7     2
  4.  / \   / \
  5. 9   6 3   1

分析

这题是大名鼎鼎的 Homebrew 的作者 Max Howell 在 Twitter 上发牢骚的那道题。原始 Tweet 地址：https://twitter.com/mxcl/status/608682016205344768

这题最简单的办法，是层次遍历，每次交换左右子树。

但是，这题也可以用递归解决，代码非常短。

解法1 层次遍历

  1. // Invert Binary Tree
  2. // Time Complexity: O(n), Space Complexity: O(n)
  3. public class Solution {
  4.     public TreeNode invertTree(TreeNode root) {
  5.         Queue<TreeNode> q = new LinkedList<>();
  6.         if (root != null) q.offer(root);
  8.         while (!q.isEmpty()) {
  9.             TreeNode node = q.poll();
  10.             // swap left and right
  11.             TreeNode tmp = node.left;
  12.             node.left = node.right;
  13.             node.right = tmp;
  15.             if (node.left != null) q.offer(node.left);
  16.             if (node.right != null) q.offer(node.right);
  17.         }
  18.         return root;
  19.     }
  20. }

解法2 递归

  1. // Invert Binary Tree
  2. // Time Complexity: O(n), Space Complexity: O(n)
  3. public class Solution {
  4.     public TreeNode invertTree(TreeNode root) {
  5.         if (root == null) return root;
  7.         TreeNode tmp = root.left;
  8.         root.left = invertTree(root.right);
  9.         root.right = invertTree(tmp);
  11.         return root;
  12.     }
  13. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/invert-binary-tree.html