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].

 

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class Solution {

　　public ArrayList<Integer> inorderTraversal(TreeNode root) {

　　　　ArrayList<Integer> al = new ArrayList<Integer>();

　　　　if(root == null) return al;

　　　　Stack<TreeNode> s = new Stack<TreeNode>();

　　　　TreeNode node = root;

　　　　//s.push(node);

　　　　while(node != null || !s.isEmpty()){

　　　　　　if(node != null){

　　　　　　　　s.push(node);

　　　　　　　　node = node.left;

　　　　　　　　continue;

　　　　　　}

　　　　　　node = s.pop();

　　　　　　al.add(node.val);

　　　　　　node = node.right;

　　　　}

　　　　return al;

　　}

}