Given a binary tree, return the preorder traversal of its nodes' values.
Example
Given:
1
/ \
2 3
/ \
4 5
return [1,2,4,5,3].
Challenge
Can you do it without recursion?
思路
解法一:
Traverse
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); traverse(root, result); return result; } public void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } result.add(root.val); traverse(root.left, result); traverse(root.right, result); } }
解法二:
Divide & Conquer
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } ArrayList<Integer> left = preorderTraversal(root.left); ArrayList<Integer> right = preorderTraversal(root.right); result.add(root.val); result.addAll(left); result.addAll(right); return result; } }
解法三:
Iterative
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Preorder in ArrayList which contains node values. */ public ArrayList<Integer> preorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return result; } }