Leetcode Invert Binary Tree
Tags: Algorithm, LeetCode, TreeInvert a binary tree.
|
1 2 3 4 5 |
4 / \ 2 7 / \ / \ 1 3 6 9 |
to
|
1 2 3 4 5 |
4 / \ 7 2 / \ / \ 9 6 3 1 |
Trivia:
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.
Analysis
This problem can be solved by using both recursion and bread first traverse or Level order traverse.
We first invert the left tree and right tree, then put the inverted right tree as the left child, and the inverted left tree as right child.
See the following recursive algorithm in Java.
Java Solution
|
1 2 3 4 5 6 7 8 9 10 |
public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return root; TreeNode leftInvert = invertTree(root.left); TreeNode rightInvert = invertTree(root.right); root.left = rightInvert; root.right = leftInvert; return root; } } |
Java Solution - Level order traverse
In the process of level order traverse of the tree, we swap the left child and right child, then we put the new left child before the new right child in the queue. We keep doing this until all the children are visited.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) return root; Queue<TreeNode> q = new LinkedList<>(); q.add(root); while(!q.isEmpty()){ TreeNode cur = q.poll(); // swap left and right child TreeNode temp = cur.right; cur.right = cur.left; cur.left = temp; // put the new left, right child into the queue, left is before right if(cur.left != null) q.add(cur.left); if(cur.right != null) q.add(cur.right); } return root; } } |
