首页 > 代码库 > *Binary Tree Inorder Traversal
*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
*Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。