题目描述（中等难度）

二叉树的先序遍历。

思路分析

之前做过 94 题 的中序遍历，先序遍历的话代码可以直接拿过来用，只需要改一改 list.add 的位置。

解法一 递归

递归很好理解了，代码也是最简洁的。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); preorderTraversalHelper(root, list); return list; } private void preorderTraversalHelper(TreeNode root, List<Integer> list) { if (root == null) { return; } list.add(root.val); preorderTraversalHelper(root.left, list); preorderTraversalHelper(root.right, list); } 

解法二 栈

第一种思路就是利用栈去模拟上边的递归。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { list.add(cur.val); stack.push(cur); cur = cur.left; //考虑左子树 }else { //节点为空，就出栈 cur = stack.pop(); //考虑右子树 cur = cur.right; } } return list; } 

第二种思路的话，我们还可以将左右子树分别压栈，然后每次从栈里取元素。需要注意的是，因为我们应该先访问左子树，而栈的话是先进后出，所以我们压栈先压右子树。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null) { return list; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); if (cur == null) { continue; } list.add(cur.val); stack.push(cur.right); stack.push(cur.left); } return list; } 

解法三 Morris Traversal

上边的两种解法，空间复杂度都是 O(n)，利用 Morris Traversal 可以使得空间复杂度变为 O(1)。

它的主要思想就是利用叶子节点的左右子树是 null ，所以我们可以利用这个空间去存我们需要的节点，详细的可以参考 94 题 中序遍历。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); TreeNode cur = root; while (cur != null) { //情况 1 if (cur.left == null) { list.add(cur.val); cur = cur.right; } else { //找左子树最右边的节点 TreeNode pre = cur.left; while (pre.right != null && pre.right != cur) { pre = pre.right; } //情况 2.1 if (pre.right == null) { list.add(cur.val); pre.right = cur; cur = cur.left; } //情况 2.2 if (pre.right == cur) { pre.right = null; //这里可以恢复为 null cur = cur.right; } } } return list; } 

总

和 94 题 没什么差别，解法三利用已有空间去存东西，从而降低空间复杂度的思想经常用到。