[leetcode - Bliend-75 ] 226. Invert Binary Tree (Easy)

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

给一个 tree 的 root 将该 tree 中所有 node 的左右 node 交换。

Example

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

BFS

要解这题要先了解什么是 BFS (广度搜寻)，简单来说就是以 layer 来遍历 tree，从第一层开始往下一层一层的遍历整颗 tree。

Coding

function bfs() {    let queue = [this.root], res = [];    while (queue.length !== 0) {      let size = queue.length;      const levelNode = [];      while (size) {        const node = queue.shift();        levelNode.push(node.val);        if (node.left) queue.push(node.left);        if (node.right) queue.push(node.right);        size--;      }      res.push(...levelNode);    }    return res;}

利用一个 queue 存处每一层的 node，利用 size 纪录每一层共有几个 node，并利用 queue 的 FIFO 特性，把该层的每一个 node 拿出来并判断该 node 是否有 left 或 right node，如果有就将他放近 queue 中。

invertTree

该题也用 bfs 的方式遍历每一层，把每一层的 left node 和 right node 交换即可

coding - while

var invertTree = function (root) {  let queue = [root];  while (queue.length !== 0) {    let size = queue.length;    while (size) {      const node = queue.shift();      if (!node.left && !node.right) {        size--;        continue;      }      const tmpL = node.left;      node.left = node.right;      node.right = tmpL;      if (node.left) queue.push(node.left);      if (node.right) queue.push(node.right);      size--;    }  }  return root;};

Coding - recursion

也可以利用 recursion 的方式先交换 left node 后再交换 right node

function invert(node) {  if (node === null) return;    const tmp = node.left;  node.left = node.right;  node.right = tmp;    invert(node.left);  invert(node.right);}var invertTree = function(root) {  invert(root)  return root}

Time complexity: O(n)