# Invert Binary Tree

### 描述​

Invert a binary tree.

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

to

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

### 解法 1 层次遍历​

// Invert Binary Tree// Time Complexity: O(n), Space Complexity: O(n)public class Solution {    public TreeNode invertTree(TreeNode root) {        Queue<TreeNode> q = new LinkedList<>();        if (root != null) q.offer(root);        while (!q.isEmpty()) {            TreeNode node = q.poll();            // swap left and right            TreeNode tmp = node.left;            node.left = node.right;            node.right = tmp;            if (node.left != null) q.offer(node.left);            if (node.right != null) q.offer(node.right);        }        return root;    }}

### 解法 2 递归​

// Invert Binary Tree// Time Complexity: O(n), Space Complexity: O(n)public class Solution {    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;    }}