找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: pls331
收起左侧

[Facebook] Facebook Intern面经

[复制链接]

4

主题

0

精华

59

积分

资深会员

Rank: 2

积分
59
发表于 12-17-2016 07:30 PM | 显示全部楼层
pls331 发表于 12-17-2016 12:33 PM
! R% {: N. j' R# ^6 c可以具体一点吗?Morris Traversal好像在哪儿听过。
8 F5 I8 r& v2 h* A2 S0 f
    List<TreeNode> inorder(TreeNode node1, TreeNode node2){
' T  j5 R  Y& G% _        List<TreeNode> res = new ArrayList<>();5 N! C& k& |/ B
        TreeNode curNode1 = node1, curNode2 = node2;' |# h4 Y5 B% F8 k
        TreeNode preNode1 = null, preNode2 = null;: m5 S7 O4 i  k$ {& H9 o* i
        while(curNode1 != null ){
9 R2 T# j! N, e3 L9 q            if(curNode1.left == null ){
# l, H9 E7 y4 r! z9 @3 T+ `                if(curNode1.val != curNode2.val) {) K+ w" `- i1 a- P1 O" `
                    res.add(curNode1);. }" a. q+ Y: V" ]/ i  T2 m" `
                    res.add(curNode2);
" X# T/ Z( a* g8 I9 S" E" J                    break;, a6 n* m( p  J# f
                }* x! O. D" w; Q+ O5 N! B: _2 g
                curNode1 = curNode1.right;
! e6 I7 V" G7 ]                curNode2 = curNode2.right;
, a* [" ], N5 E4 f% B8 @* L6 ?            }else{8 Y4 w+ |7 B/ r
                preNode1 = curNode1.left;
4 X' ^4 D6 k1 w' Z- d& p6 t                preNode2 = curNode2.left;
5 \# w0 A8 j1 e6 r                while(preNode1.right != null && preNode1.right != curNode1){
: u  d& ~. [: ]( h                    preNode1 = preNode1.right;% M0 T: n6 V* N1 ^/ L( {7 C
                    preNode2 = preNode2.right;
, u7 r9 Y7 Q% i) g2 E; E                }
) J3 M% p3 q9 ?/ s$ t2 P# s                if(preNode1.right == null){; J3 I, d. u. s
                    preNode1.right = curNode1;" N% y3 z9 `, V$ B" N6 Z- S
                    curNode1 = curNode1.left;1 F. q: |* r: o( t% u
                    preNode2.right = curNode2;# h* A7 `: Z' \6 r; J
                    curNode2 = curNode2.left;
  e7 \1 n1 H7 g! k" A                }else{
5 P! k+ F3 J# N6 a3 d7 y                    preNode1.right = null;   // recover the original tree structure  ?1 l7 \+ g5 C. s5 Z- Z
                    preNode2.right = null;/ e$ h- ~+ V8 V# G
                    if(curNode1.val != curNode2.val) {1 O: D' W; l' R+ h2 N" @
                        res.add(curNode1);
4 J* B# y, \1 Y                        res.add(curNode2);
' \* @! `7 L7 p; ]/ D% z, i                        break;# r( [4 k7 x+ }! ~2 e( D
                    }
9 y( ^9 F7 J$ ^# B6 |1 ?                    curNode1 = curNode1.right;/ m# @" s- K0 S7 k8 R; x
                    curNode2 = curNode2.right;7 f, g; A7 c6 C; z8 _+ Y
                }
! h: S8 z. e2 o2 a& u& B% ^0 k            }9 E% g* ]/ }0 V
        }
+ w& f3 w1 V+ V/ Z        return res;  w' b, j" m. X% x' S7 W
    }$ w* r  ], e6 y; Z$ N( P
欢迎指正
# j% y. X% R# u) f% o& X& y. `* K5 v! W

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, ]; W% z$ `5 [) J) U* e8 J4 \, H: k
給你按個讚
  Q1 q1 ?( R8 H$ X& Y
多谢多谢
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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