|
|
发表于 12-17-2016 07:30 PM
|
显示全部楼层
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 |
|
楼主: pls331
楼主