[LeetCode][JavaScript]Invert Binary Tree 反转二叉树

雨点打透心脏的1/2处 2022-01-20 00:31 188阅读 0赞

### 反转二叉树 ###

*  其实我从没有想到前端面试会问到这个问题，题目来源于google的面试

> Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off. (我们90%的工程师都用你写的软件但是我们不能聘用你)

吊吊吊，著名homebrew的初创者Howell前往google面试ios开发，结果还没问到ios技术问题的时候就已经挂了，而且死在反转二叉树，有那么点意思。果然title在我g厂面试还是渣渣，我g厂从不缺title

我这个代码也是在网上看到的，直接抄过来的[知乎][Link 1]

class Solution:
        # @param {TreeNode} root
        # @return {TreeNode}
        def invertTree(self, root):
            from Queue import Queue
            q = Queue()
            q.put(root)
    
            while not q.empty():
                node = q.get()
                if not node:
                    continue
                node.left, node.right = node.right, node.left
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
    
            return root
    复制代码

这个类写的老夫懵逼了，老夫在git上看到一个简单一点的方法，顺便也贴出来把

function binaryTree(node) {
            if(!node) return
            let left = binaryTree(node.left)
            let right = binaryTree(node.right)
            if(left) node.left = right
            if(right) node.right = left
            return node
        }
    复制代码

突然想到可能很多同学对二叉树没什么概念，我就把这个类似的树写出来吧

let tree  = {
        left: {
            left: {
                value: 1
            },
            right: {
                value: 2
            },
            value: 3
        },
        right: {
            left: {
                value: 6
            },
            right: {
                value: 7
            },
            value: 8
        },
        value: 10
    }
    复制代码

[Link 1]: https://link.juejin.im?target=https%3A%2F%2Fzhuanlan.zhihu.com%2Fp%2F20077125