1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Binary Tree Inorder Traversal
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
7+ Notes:
8+ Given a binary tree, return the inorder traversal of its nodes' values.
9+ For example:
10+ Given binary tree {1,#,2,3},
11+ 1
12+ \
13+ 2
14+ /
15+ 3
16+ return [1,3,2].
17+ Note: Recursive solution is trivial, could you do it iteratively?
18+
19+ Solution: 1. Recursive solution. Time: O(n), Space: O(n).
20+ 2. Iterative way (stack). Time: O(n), Space: O(n).
21+ 3. Threaded tree (Morris). Time: O(n), Space: O(1).
22+ */
23+
24+ /**
25+ * Definition for binary tree
26+ * public class TreeNode {
27+ * int val;
28+ * TreeNode left;
29+ * TreeNode right;
30+ * TreeNode(int x) { val = x; }
31+ * }
32+ */
33+ public class Solution {
34+ public List <Integer >inorderTraversal_1 (TreeNode root ) {
35+ List <Integer >res =new ArrayList <Integer >();
36+ if (root ==null )return res ;
37+ inorder (root ,res );
38+ return res ;
39+ }
40+ public void inorder (TreeNode root ,List <Integer >res ) {
41+ if (root ==null )return ;
42+ inorder (root .left ,res );
43+ res .add (root .val );
44+ inorder (root .right ,res );
45+ }
46+ public List <Integer >inorderTraversal_2 (TreeNode root ) {
47+ List <Integer >res =new ArrayList <Integer >();
48+ Stack <TreeNode >stk =new Stack <TreeNode >();
49+ TreeNode cur =root ;
50+ while (stk .isEmpty () ==false ||cur !=null ) {
51+ if (cur !=null ) {
52+ stk .push (cur );
53+ cur =cur .left ;
54+ }else {
55+ cur =stk .pop ();
56+ res .add (cur .val );
57+ cur =cur .right ;
58+ }
59+ }
60+ return res ;
61+ }
62+ public List <Integer >inorderTraversal (TreeNode root ) {
63+ List <Integer >res =new ArrayList <Integer >();
64+ TreeNode cur =root ;
65+ while (cur !=null ) {
66+ if (cur .left ==null ) {
67+ res .add (cur .val );
68+ cur =cur .right ;
69+ }else {
70+ TreeNode node =cur .left ;
71+ while (node .right !=null &&node .right !=cur )
72+ node =node .right ;
73+ if (node .right ==null ) {
74+ node .right =cur ;
75+ cur =cur .left ;
76+ }else {
77+ res .add (cur .val );
78+ node .right =null ;
79+ cur =cur .right ;
80+ }
81+ }
82+ }
83+ return res ;
84+ }
85+ }
