Problem
Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
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 f*** off.
Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if (root) {
swap(root);
invertTree(root.left);
invertTree(root.right);
}
return root;
};
var swap = function (node) {
var left = node.left;
node.left = node.right;
node.right = left;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).