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?
// Iterative 先用一个stack把中间节点存下来,左边如果为空就pop出来存进result然后换到right child
public class Solution { public List inorderTraversal(TreeNode root) { ArrayList result = new ArrayList<>(); if(root == null){ return result; } Stack stack = new Stack<>(); TreeNode p = root; while(!stack.isEmpty() || p != null){ if(p != null){ stack.push(p); p = p.left; }else{ TreeNode temp = stack.pop(); result.add(temp.val); p = temp.right; } } return result; } } // Recursive public class Solution { public List inorderTraversal(TreeNode root) { ArrayList result = new ArrayList<>(); inorder(root, result); return result; } public void inorder(TreeNode root, ArrayList result){ if(root == null){ return; } inorder(root.left, result); result.add(root.val); inorder(root.right, result); } }