Tuesday, September 1, 2015

Leetcode: Invert Binary Tree

Invert a binary tree.
     4
   /   \
  2     7
 / \   / \
1   3 6   9
to
     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.
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