- 51.8%
https://leetcode.com/problems/invert-binary-tree/#/description
1 | Invert a binary tree. |
Trivia:
This problem was inspired by this original tweet by Max Howell:
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.
对应剑指offer 19题
三种方法:递归、DFS、BFS
方法一:递归
1 | public class Solution { |
我的实现:
1 | class Solution { |
我的代码实现:
1 | /** |
方法二:DFS,使用栈作为辅助,使用栈的方法是把root压入栈,栈不为空时,弹出当前栈顶,针对栈顶的左右节点进行反转,若左非空,左压入,右非空,右压入
1 | public class Solution { |
方法三:
BFS,层序遍历的方法,注意,要把层序当做先序,中序,后续遍历一样普通和容易想到的方法。
层序遍历,具体cpp实现,还需要再思考。
1 | public class Solution { |
https://discuss.leetcode.com/topic/16138/recursive-and-non-recursive-c-both-4ms/3
Recursive and non-recursive C++ both 4ms
Recursive
1 | TreeNode* invertTree(TreeNode* root) { |
Non-Recursive
1 | TreeNode* invertTree(TreeNode* root) { |
https://discuss.leetcode.com/topic/16062/3-4-lines-python/4
3-4 lines Python
1 | def invertTree(self, root): |
Maybe make it four lines for better readability:
1 | def invertTree(self, root): |
And an iterative version using my own stack:
1 | def invertTree(self, root): |
https://discuss.leetcode.com/topic/21271/python-solutions-recursively-dfs-bfs
Python solutions (recursively, dfs, bfs).
1 | # recursively |
https://discuss.leetcode.com/topic/16039/straightforward-dfs-recursive-iterative-bfs-solutions/3
Straightforward DFS recursive, iterative, BFS solutions
As in many other cases this problem has more than one possible solutions:
Lets start with straightforward - recursive DFS - it’s easy to write and pretty much concise.
1 | public class Solution { |
The above solution is correct, but it is also bound to the application stack, which means that it’s no so much scalable - (you can find the problem size that will overflow the stack and crash your application), so more robust solution would be to use stack data structure.
1 | public class Solution { |
Finally we can easly convert the above solution to BFS - or so called level order traversal.
1 | public class Solution { |
If I can write this code, does it mean I can get job at Google? ;)