Binary Tree Inorder Traversal
问题：
Given a binary tree, return the inorder traversal of its nodes‘ values.
Recursive solution is trivial, could you do it iteratively?
思路：
栈的方法 一直加入左节点，直到无法加入的话，弹出，弹出时观测有节点
我的代码：
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); do { TreeNode node = stack.peek(); if(node.left == null) { list.add(node.val); stack.pop(); if(node.right != null) { stack.push(node.right); } } else { stack.push(node.left); node.left = null; } }while(!stack.isEmpty()); return list; } }
他人代码：
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; while(cur!=null || !stack.empty()){ while(cur!=null){ stack.add(cur); cur = cur.left; } cur = stack.pop(); list.add(cur.val); cur = cur.right; } return list; }
学习之处：
原文：http://www.cnblogs.com/sunshisonghit/p/4313411.html
