java 翻转二叉树

这是Google面试时的一道算法题,某个dalao因为做不出这道算法题被拒绝了(很惨),此次事件后来被当做话题在知乎上讨论了。

我刚开始先入为主地觉得这道题一定有玄机,后来仔细一想,发现只是遍历一下再交换左右节点而已…

参考:https://www.zhihu.com/question/31202353?rf=31187043

 

一、问题

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

Invert a binary tree.

to

这道题有个不太友好的描述(典故),默哀:

This problem was inspired by this original tweet by Max Howell(就是出事的dalao):

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.

二、解题思路

深度遍历二叉树中的所有节点,进行左右子节点的互换,一直递归下去。

InvertBinaryTree.java

后来发现一篇回答的解题思路和我一模一样。

这道题的官方答案为:

实现效果都是一样的。

三、总结

所以说基础还是要扎实,不然就得fuck off。

发表评论

电子邮件地址不会被公开。 必填项已用*标注