226. Invert Binary Tree

Leetcode

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

題目

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

解答

• 方法一

Recursion

var invertTree = function(root) {
    if (root === null) return null;
    invertTree(root.left);
    invertTree(root.right);
    [root.left, root.right] = [root.right, root.left];
    return root;
};

Runtime: 81 ms, faster than 58.32% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 42.3 MB, less than 54.64% of JavaScript online submissions for Invert Binary Tree.

• 方法二

Iteration

var invertTree = function(root) {
    if(root === null) return null;
    
    const queue = [root];
    while (queue.length) {
        const node = queue.shift();
        [node.left, node.right] = [node.right, node.left];
        if(node.left) queue.push(node.left);
        if(node.right) queue.push(node.right);
    }
    return root;
};

Runtime: 116 ms, faster than 14.73% of JavaScript online submissions for Invert Binary Tree.

Memory Usage: 42.6 MB, less than 18.98% of JavaScript online submissions for Invert Binary Tree.