> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-04-2022-226.-invert-binary-tree.md).

# 04/04/2022 226. Invert Binary Tree

Method 1: DFS. used preorder traversal. first swap the root's left and right, then invertTree of the left tree and invertTree of the right tree.

Time O(N)

Space O(H)

```
// Some code
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        swap(root);
        invertTree(root.left);
        invertTree(root.right);   
        
        return root;       
    }
    
    private void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
```

Method2 : BFS. Use queue to add node in each level. When processing each node, swap its left and right and then add its left and right to the queue again.

Time O(N)

Space O(N)

```
// Some code
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode curr = queue.poll();
            swap(curr);
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
        }
        return root;
    }
    
    private void swap(TreeNode root){
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
```