leetcode Binary Tree Inorder Traversal

gistfile1.md

###leetcode Binary Tree Inorder Traversal

####思路

• 循环遍历找到树的最左的节点，同时在stack中遍历过的每一个节点。
• 然后从栈顶弹出元素，直到stack为空。将该元素加入结果列表。判断该元素是否有右孩子，如果有，加入到stack中；遍历找到该右孩子的最左节点，都加入stack中，重复循环。

####java代码

/**
 * 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) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> rets = new ArrayList<Integer>();
      LinkedList<TreeNode> stack  = new LinkedList<TreeNode>();
    	TreeNode left = root;
    	while (null != left) {
    		stack.addFirst(left);
    		left = left.left;
    	}
    	while (!stack.isEmpty()) {
    		TreeNode node = stack.removeFirst();
    		rets.add(node.val);
    		if (null != node.right) {
    			stack.addFirst(node.right);
    			left = node.right.left;
    			while(null != left) {
    				stack.addFirst(left);
                    left = left.left;
    			}
    		}
    	}
    	return rets;
    }
}