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