数据结构算法（二叉树遍历方法）

题目描述（中等难度）

二叉树的先序遍历。

思路分析

之前做过的中序遍历，先序遍历的话代码可以直接拿过来用，只需要改一改 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; } 

参考文献

• https://blog.csdn.net/weixin_35770067/article/details/105007033

本文地址：https://blog.csdn.net/weixin_35770067/article/details/108018362