[Leetcode] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

使用递归写很好写，使用iterative的方法的话需要使用Morris遍历

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        return list;
    }
    
    public void inorder(TreeNode root, List<Integer> list) {
        if(root == null) return;
        else {
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        TreeNode cur = root, temp;
        
        while(cur != null) {
            if(cur.left == null) {
                list.add(cur.val);
                cur = cur.right;
            }
            else {
                temp = cur.left;
                while(temp.right != null && temp.right != cur) temp = temp.right;
                if(temp.right == null) {
                    temp.right = cur;
                    cur = cur.left;
                }
                else {
                    list.add(cur.val);
                    temp.right = null;
                    cur = cur.right;
                }
            }
        }
        
        return list;
    }