基础算法之二叉树前序遍历

前序遍历是二叉树遍历方法的一种，和中序遍历、后续遍历是二叉树最常见的遍历方式。

适用场景

前序遍历适用于目录现实、组织结构图显示等。

遍历顺序

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

递归法

按照遍历顺序递归即可，递归结束条件，当递归到空节点时，递归结束。

public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); preorder(root, res); return res; } public void preorder(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); preorder(root.left, res); preorder(root.right, res); } 迭代法

迭代法的原理时用一个栈，使用栈后进先出的特性来保存递归顺序，如果当前节点有子节点，按照右做的顺序压入堆栈，下一次循环取栈顶元素，循环上述过程。
比如：

3 / \ 9 20 / \ 15 7

将3压入堆栈

循环堆栈，取出栈顶元素3，将3的右节点20压入堆栈，再将左节点9压入堆栈

再次循环，取出栈顶元素9，将9的右左子节点null,分别压入堆栈

再次循环，取出栈顶元素null, continue到下一次循环

重复上面2-4步，直至堆栈为空

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