翻转二叉树

原创

_kyle

修改于 2020-12-14 06:10:07

26500

代码可运行

文章被收录于专栏：kyle的专栏kyle的专栏

运行总次数：0

代码可运行

题目描述

翻转一棵二叉树。

示例：

输入：

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

输出：

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

备注:

这个问题是受到 Max Howell 的原问题启发的：

谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

解题思路

广度优先搜索

使用队列，当队列中有元素时，则对依次出列，并对当前元素通过中间变量进行左右交换，若交换后的元素存在，则再进入队列。

const invertTree = function(root) {
    if (!root) return null
    const queue = [root]

    while(queue.length){
        let node = queue.shift()
        let temp = node.left
        node.left = node.right
        node.right = temp

        if (node.left)
            queue.push(node.left)
        if (node.right)
            queue.push(node.right)
    }

    return root
};

简化代码

const invertTree = function(root) {
    if (!root) return null
    const queue = [root]

    while(queue.length){
        let 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
};

递归

当前函数进行左右节点交换，若左节点或右节点存在，则再次对存在节点调用invertTree函数。需要注意的是当根节点为空时，则直接返回null。

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

    if (root.left) invertTree(root.left)
    if (root.right) invertTree(root.right)

    return root
};