*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?

 

题解：

中序遍历：递归左 处理当前 递归右。

 

解法一：递归代码如下：

1 public void helper(TreeNode root, ArrayList<Integer> re){ 2 if(root==null) 3 return; 4 helper(root.left,re); 5 re.add(root.val); 6 helper(root.right,re); 7 } 8 public ArrayList<Integer> inorderTraversal(TreeNode root) { 9 ArrayList<Integer> re = new ArrayList<Integer>(); 10 if(root==null) 11 return re; 12 helper(root,re); 13 return re; 14 }

 

解法二：非递归解法

1 public ArrayList<Integer> inorderTraversal(TreeNode root) { 2 ArrayList<Integer> res = new ArrayList<Integer>(); 3 if(root == null) 4 return res; 5 LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); 6 while(root!=null || !stack.isEmpty()){ 7 if(root!=null){ 8 stack.push(root); 9 root = root.left; 10 }else{ 11 root = stack.pop(); 12 res.add(root.val); 13 root = root.right; 14 } 15 } 16 return res; 17 }

 

reference：http://www.cnblogs.com/springfor/p/3877179.html

转载于:https://www.cnblogs.com/hygeia/p/4709807.html

相关资源：JAVA上百实例源码以及开源项目