脸书 电面

防水的题 第一眼  我也没思路 ——>去刷题，要努力哦，加油！ 昨晚刷到凌晨1点。

alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。（没有root）
因为是完全树（每个pare ...

输入时所有的leaves？

iPhD 发表于 2016-9-2 09:03
能说具体点吗？或给个伪代码？怎么改？

哦哦 理解错了 直接给你的就是改过的leaf node么？那就直接向上改就行了吧

alucardzhou 发表于 2016-9-2 10:00
不用postorder遍历。别想复杂了。
输入就是个leaf node。（没有root）
因为是完全树（每个pare ...

运气可以啊 ！ 祝lz早日拿到offer

houqingniao 发表于 2016-9-2 10:32
输入时所有的leaves？

只改一个leaf 所以输入就是那个leaf

第一题感觉直接走一遍从leaf到root的path就行了？(depending on 树的值，未必需要完全走完)

1. void invert(TreeNode n) {
   
2.     while (n != null) {
   
3.         n.val ^= 1;
   
4.         if (n.parent != null) {
   
5.             if (n.parent.left == n) {
   
6.                 if (n.parent.right.val == 0) break;
   
7.             } else {
   
8.                 if (n.parent.left.val == 0) break;
   
9.             }
   
10.         }
    
11.         n = n.parent;
    
12.     }
    
13. }

复制代码

Sorrow雨 发表于 2016-9-1 22:03
哦哦 理解错了 直接给你的就是改过的leaf node么？那就直接向上改就行了吧

正解！就是这个意思

wzs9988 发表于 2016-9-1 22:32
第一题感觉直接走一遍从leaf到root的path就行了？(depending on 树的值，未必需要完全走完)

是的是的。
所以最后在复杂度的讨论部分有点意思。
最优是O(1)，最差是（logN）
但是小哥引进了概率。每次parent翻牌子的几率只有1/4.
所以平均时间复杂度比logN要低。他说是O（1）。
这里我也没太理解。

alucardzhou 发表于 2016-9-2 12:52
是的是的。
所以最后在复杂度的讨论部分有点意思。
最优是O(1)，最差是（logN）

谢谢Lz分享，请问每次parent翻牌子的概率为什么是1/4? 感觉是1/2呀，两个孩子的值有四种可能（1 1，0 0, 1 0, 0 1）, 假设被翻的是前面的孩子， 那么第1、4种情况下，翻了孩子之后parent的值都会变

hzyslddm 发表于 2016-9-2 01:36
谢谢Lz分享，请问每次parent翻牌子的概率为什么是1/4? 感觉是1/2呀，两个孩子的值有四种可能（1 1，0 0,  ...

你说得对对。可能是我记错了。
说实话自己当时很紧张。
十分害怕碰到什么写json啊，什么不排序找等差数列那样的神题。
那么这种情况下时间复杂度应该是O（1）么？还是仍然是O（logN）呢？