144. Binary Tree Preorder Traversal 发表于 2021-11-12 Recursion123456789101112131415161718192021class Solution { public List<Integer> preorderTraversal(TreeNode root) { // root, left, right List<Integer> list = new LinkedList<>(); recur(list, root); return list; } private void recur(List<Integer> list, TreeNode node) { if (node == null) { return; } list.add(node.val); recur(list, node.left); recur(list, node.right); }} Iterate1234567891011121314151617181920212223242526class Solution { public List<Integer> preorderTraversal(TreeNode root) { // root, left, right List<Integer> list = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if (root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode node = stack.pop(); list.add(node.val); // 注意放入 stack 的顺序,因为 pop 出来的顺序与 push 的顺序相反 if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return list; }} Iterate12345678910111213141516171819202122class Solution { public List<Integer> preorderTraversal(TreeNode root) { // root, left, right List<Integer> numList = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { while (root != null) { numList.add(root.val); stack.push(root); root = root.left; } // now: root is null TreeNode node = stack.pop(); root = node.right; } return numList; }} Reference144. Binary Tree Preorder Traversal