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?
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<Integer>(); if(root == null) return list; if(root.left!= null){ list.addAll(inorderTraversal(root.left)); } list.add(root.val); if(root.right!= null){ list.addAll(inorderTraversal(root.right)); } return list; } }
public class Solution { public ArrayList<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode current = root; while(!stack.isEmpty() || current != null){ if(current!= null){ stack.push(current); current = current.left; } else{ current = stack.pop(); list.add(current.val); current = current.right; } } return list; } }
mistakes: wrong understand of stack method
learned: left-most first ,then the parent node will be on top of the stack