Description
Given a binary tree, return the preorder traversal of its nodes’ values.
Example
1 2 3 4 5 6 7 8
| Input: [1,null,2,3] 1 \ 2 / 3
Output: [1,2,3]
|
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
|
class Solution { List<Integer> res = new ArrayList<>(); public void preOrder(TreeNode node){ res.add(node.val); if (node.left != null) preOrder(node.left); if (node.right != null) preOrder(node.right); return; } public List<Integer> preorderTraversal(TreeNode root){ if (root == null) return res; List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.add(p.val); p = p.left; } else { TreeNode node = stack.pop(); p = node.right; } } return result; } }
|