leetcode 也是很会玩啦

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3451 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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.

这题还是easy的哦WWWWW

whiteboard

leetcode

invert

12 条回复 • 2015-06-15 11:50:21 +08:00

101

2015-06-13 17:44:45 +08:00

http://www.zhihu.com/question/31202353

ryd994

2015-06-14 09:50:46 +08:00 via Android

目前看见最好的就是强制cast指针，除了可移植性可能不太好之外
还有什么能比O(1)更快……

kcworms

2015-06-14 12:56:18 +08:00

@ryd994 怎么做才能O(1)呢？难道你说的是保持二叉树本身不变，访问的时候翻转地访问左右子树？

msg7086

2015-06-15 00:32:20 +08:00

@kcworms 相当于交换对象方法的函数地址。
用ruby的话来说，就相当于
alias :temp, :left
alias :left, :right
alias :right, :temp

这样本来你访问n.left的时候，就变成调用Node::right()了。

估计只对动态语言有效？

ryd994

2015-06-15 02:23:46 +08:00

@msg7086 C有效啊
只要编译器不要瞎重排struct里的内存分配就行

msg7086

2015-06-15 02:39:58 +08:00

@ryd994 求个AC的代码观摩下～

ryd994

2015-06-15 02:45:23 +08:00

@msg7086 /t/197730 48楼那个应该可以吧

msg7086

2015-06-15 03:23:05 +08:00

@ryd994 我觉得这个应该AC不了吧。
静态语言取数据是跟着地址走。动态语言才是当场根据方法名来求值的吧。

ryd994

2015-06-15 03:28:28 +08:00

@msg7086 这个编译的时候就可以知道啊

ryd994

2015-06-15 03:32:28 +08:00

@msg7086 只是编译器取指针时如何解释的区别
原本left编译成left的地址，现在left编译为right的地址

msg7086

2015-06-15 03:35:41 +08:00

@ryd994 但是对于online judge来说，判断答题是否正确的代码是不可能被你修改的吧。
如果是Ruby的话强行Monkey Patch进Meta Class大概还有可能AC，C语言我觉得没戏。
你可以试试？

kcworms

2015-06-15 11:50:21 +08:00

@msg7086 #7里提到的方法和修改二叉树本身有区别。如果是aReverseNode->left->left->right这样访问没问题，但代码里有其他参数为NormalNode的函数就不好使了，需要全部改掉。