LeetCode Notes: Invert Binary Tree

#leetcode

Question

Flip a binary tree.

Example:

enter:

// Before flipping
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

// After flipping
     4
   /   \
  7     2
 / \   / \
9   6 3   1

Remarks: This question was inspired by Original Question 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**k off.

Solution

Analysis:

Recurse all the left and right subtrees, swap the left and right subtrees

Code:

/**
  * Definition for a binary tree node.
  * function TreeNode(val, left, right) {
  * this.val = (val===undefined? 0: val)
  * this.left = (left===undefined? null: left)
  * this.right = (right===undefined? null: right)
  *}
  */
/**
  * @param {TreeNode} root
  * @return {TreeNode}
  */
var invertTree = function(root) {

     // no more subtrees
     if(root == null) return null

     // swap the subtrees on both sides
     const treeNode = root.left
     root.left = root.right
     root.right = treeNode
    
     // Recursively set the subtrees on both sides
     invertTree(root.left)
     invertTree(root.right)

     return root

};

Reference

Comments