Invert a binary tree.

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

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

This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

**Understand the problem:**

The problem is very easy to understand. Just to re-link root's left child to the right sub-tree, and root's right child to the left sub-tree. Only one thing to note is we must use a temp Node when we do the swap.

Code (Java):

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

**A BFS Solution:**

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

## No comments:

## Post a Comment