找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: pls331
收起左侧

[Facebook] Facebook Intern面经

[复制链接]

4

主题

0

精华

59

积分

资深会员

Rank: 2

积分
59
发表于 12-17-2016 07:30 PM | 显示全部楼层
pls331 发表于 12-17-2016 12:33 PM
8 A* T! P3 z2 Z* J( [可以具体一点吗?Morris Traversal好像在哪儿听过。
3 u9 e4 c) _! g2 d+ w
    List<TreeNode> inorder(TreeNode node1, TreeNode node2){
3 x" }) M  K0 k4 p- W) [        List<TreeNode> res = new ArrayList<>();
" H' j$ H8 \- `; M! q        TreeNode curNode1 = node1, curNode2 = node2;
3 Y5 x  N3 @3 J0 F7 q% m4 a: H# g9 D        TreeNode preNode1 = null, preNode2 = null;5 F& ]% \+ ^6 V, a4 W) `* x3 }
        while(curNode1 != null ){
* m1 F: J1 U. ^0 _# ^; `2 O; M            if(curNode1.left == null ){
+ U# o* b1 u+ f6 A) m9 w1 P                if(curNode1.val != curNode2.val) {( }4 e4 s* H: C/ i
                    res.add(curNode1);
' k- f' x+ i0 x7 G% w                    res.add(curNode2);" J1 \) i4 r- i. K: p1 p
                    break;
% E: S$ J5 B; v) {% H2 k                }
6 t0 V/ x) ]" E, B5 _0 u                curNode1 = curNode1.right;1 ]( d8 E& {* i
                curNode2 = curNode2.right;
* k. u/ z; G$ ^" a8 {( A1 f% A            }else{# K( j) L+ y; i/ y  @
                preNode1 = curNode1.left;( `' d% @8 p  F
                preNode2 = curNode2.left;( z1 `& l0 s7 Z9 W: E, ]
                while(preNode1.right != null && preNode1.right != curNode1){9 a' @% ~5 t. l& i) B% `" V
                    preNode1 = preNode1.right;6 R8 }# W: s7 V
                    preNode2 = preNode2.right;
6 S" C4 L3 r/ a/ W                }: H: u* R/ Q$ y" F0 B/ x% A
                if(preNode1.right == null){
/ [9 E+ k9 b  Y9 U$ N$ X  A6 z* P5 b                    preNode1.right = curNode1;; ~2 D! e. }  ~7 q, e: R, y7 v1 o) U
                    curNode1 = curNode1.left;
1 e4 V+ X! ^2 c" i                    preNode2.right = curNode2;
! M2 V: g2 \) e6 n                    curNode2 = curNode2.left;* h+ o* \% c2 Z- _( S. i- u0 u) q
                }else{
2 B/ B( G& W4 K2 I  o: e. p) W" b                    preNode1.right = null;   // recover the original tree structure0 r) _+ y9 Z( C, E0 H/ o
                    preNode2.right = null;9 v# U: m% R2 V. k
                    if(curNode1.val != curNode2.val) {
& E, n! A8 s! K! X                        res.add(curNode1);
9 f; w. ?+ D4 t" M                        res.add(curNode2);
. k' E: {3 C% t& `8 J                        break;0 p& a  D: b$ @3 d1 Y
                    }
# I) k- v/ @, {4 A7 G( _9 ?# i/ W7 `                    curNode1 = curNode1.right;" h( Z; a5 }( Z3 }2 Y/ J$ S1 S
                    curNode2 = curNode2.right;% B% z! R. ~( M: s8 Q9 p
                }
. h0 a8 ]' q! I) D8 k            }
8 Y) ?' M& E/ o' e4 `& [# {        }' ?5 h. w3 i6 ~, f7 ~0 k4 i! x
        return res;
3 K: W+ J( ~2 O5 K+ ?    }
7 t8 y, `$ W1 t/ Q5 t欢迎指正
; L- J! J2 d8 H- B/ u5 q( G

6

主题

1

精华

62

积分

资深会员

Rank: 2

积分
62
发表于 12-26-2016 08:47 PM | 显示全部楼层
給你按個讚

5

主题

4

精华

118

积分

资深会员

Rank: 2

积分
118
 楼主| 发表于 2-2-2017 10:27 PM | 显示全部楼层
mud2man 发表于 12-26-2016 08:47 PM
7 T. M7 j- ~1 x4 g' E給你按個讚
. v# W1 y3 s' n% b1 w
多谢多谢
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表