LeetCode 226. Invert Binary Tree

题目：

Invert a binary tree.

Example:

Input:

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

Output:

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

---

Easy题，又没完全做出来，哎，想到了要recursively invert subtree，差最后一步没想到两边要反过来挂root上。时间复杂度O(n)，空间复杂度O(nlogn)。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Invert Binary Tree.

Memory Usage: 36.8 MB, less than 13.53% of Java online submissions for Invert Binary Tree.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }

迭代的做法也很简单也很巧妙。刚开始还想着用bfs的套路一层层来整，想半天不知道该怎么知道这个节点到底应该挂谁下面，没想到可以直接不用bfs的inner for loop，每次poll出一个节点，把这个节点的左右子节点交换一下再add回去就好了，哎，没想到啊。时间复杂度也是O(n)，空间，大概也是O(n)？

Runtime: 0 ms, faster than 100.00% of Java online submissions for Invert Binary Tree.

Memory Usage: 36.7 MB, less than 13.53% of Java online submissions for Invert Binary Tree.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode temp = node.left; node.left = node.right; node.right = temp; if (node.left != null) { queue.add(node.left); } if (node.right != null) { queue.add(node.right); } } return root; } }