Inverting Binary Tree

Flip a binary tree.

Example

Input:

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

Output:

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

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) return root;
    invertTree(root.left);
    invertTree(root.right);
    [root.left, root.right] = [root.right, root.left];
    return root;
};

Idea

This problem is a classic binary tree operation. It involves recursively traversing from the root node, flipping from the leaf nodes. If the current node is root, then only need to continue swapping the positions of the two subtrees to complete the flip. Firstly, check if the node exists, if not, return an empty node directly. Then recursively invert the left subtree and right subtree, and then define a destructuring assignment operation (ES6 allows to extract values from arrays and objects based on certain patterns, and assign values to variables, this is called destructuring assignment). Swap the position of the left subtree and right subtree, similar to post-order recursive traversal. Because the recursive operation is continuously flipping from the leaf nodes, finally return the root node.

Daily Topic

https://github.com/WindrunnerMax/EveryDay

Reference

https://leetcode-cn.com/problems/invert-binary-tree/