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?
先贴递归实现的吧
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 List<Integer> list = new ArrayList<Integer>(); 12 public List<Integer> inorderTraversal(TreeNode root) { 13 if(null != root){ 14 inorderTraversal(root.left); 15 list.add(root.val); 16 inorderTraversal(root.right); 17 18 19 } 20 return list; 21 } 22 }
这里要求用非递归实现，我用的堆栈
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public List<Integer> inorderTraversal(TreeNode root) { 12 List<Integer> result = new ArrayList<Integer>(); 13 Stack<TreeNode> stack = new Stack<TreeNode>(); 14 if(null == root) 15 return result; 16 17 do{ 18 while(null != root){ 19 stack.push(root); 20 root = root.left; 21 }//左子树入栈 22 TreeNode temp = stack.pop();//出栈 23 result.add(temp.val); 24 root = temp.right; 25 if(null != root) 26 { 27 stack.push(root); 28 root = root.left; 29 } 30 }while(!stack.isEmpty()); 31 32 return result; 33 } 34 }
原文：http://www.cnblogs.com/luckygxf/p/4104547.html