算法系列二之树:二叉树的前中后序遍历
大家好呀，我是饲养员，今天给大家分享一个简单的算法题，树问题：二叉树的深度遍历
144. 二叉树的前序遍历
难度:简单
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
解:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/class Solution {public List<Integer> preorderTraversal(TreeNode root) {if(root == null){return Collections.EMPTY_LIST;}List<Integer> list = new ArrayList<>();// 前序遍历:根左右list.add(root.val);list.addAll(preorderTraversal(root.left));list.addAll(preorderTraversal(root.right));return list;}}
用递归写非常简单，那么中序遍历也是第23行和24行对换即可，后序也是如此，由于这是一道简单题，我们需要尝试非递归的写法，可是思路应该怎样呢？我遍历到的节点不一定就是要的结果顺序呀，如果能够控制先进的能够后出就好了，那么这种数据结构是什么呢？栈(Stack)
来，我们试一下用非递归写一下，代码如下:
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();// 初始化一个栈，用来存放临时数据Stack<TreeNode> stack = new Stack<>();TreeNode tree = root;// 如果当前节点已经空或者栈为null，则跳出循环while(tree != null || !stack.empty()){// 正常场景下，当前树不为null，能够继续循环的情况while (tree != null) {list.add(tree.val);stack.add(tree);tree = tree.left;}// 接下来分tree == null, stack还没有完全弹出的情况，只要直接弹出即可tree = stack.pop();// 根节点和左节点分别完成，剩下右节点tree = tree.right;}return list;}}
那么中序遍历呢？
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode tree = root;while(tree != null || !stack.empty()){if (tree != null) {stack.add(tree);tree = tree.left;} else {tree = stack.pop();list.add(tree.val);tree = tree.right;}}return list;}}
总结
其实非递归方式无非就是用一个栈去临时存放树，从而达到控制存放树存放顺序这么一个作用，其实栈的用法也很简单，pop是弹出元素，add是放入元素，栈是先进后出的，前序遍历是根左右，中序是左根右，知道这些基本的概念后，解题就很容易。
好了，本期的饲养员投喂完毕，下次见！