226. Invert Binary Tree

Difficulty:
Related Topics:
Similar Questions:

    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: