二叉树的前序遍历之迭代

vlambda
2021-07-05

二叉树的前序遍历之迭代

@2021 SLIGHT HEAT

上篇文章我们写了二叉树的简介和二叉树递归前序遍历

并且在最后说了二叉树还有两种其它的遍历方式，今天我们就来详细的解析一下迭代遍历二叉树

迭代和递归的区别在于递归的时候是隐式的维护了一个栈，而在迭代的时候需要我们显式的将栈给模拟出来，其余的实现与细节都相同，看下面的图片：

右边是显式声明的栈，左边是树，树的下方是存储遍历结果的数组

第一步将F放入栈中：

第二步：将F从栈中取出放入数组，并获取到F的左子树和右子树，然后将左子树和右子树放入栈中

注意：栈是先入后出，后入先出，所以要先放右子树然后放左子树。

第三步：将左子树B从栈中取出放入数组，同时将左子树B作为根获取B的左子树和右子树，将获取到的左子树和右子树放入栈中。

注意：这里B没有左子树，也没有右子树，所以不往栈中放入数据

第四步：将F的右子树A从栈中取出放入数组，同时将A作为根获取 A的左子树和右子树，将获取到的左子树和右子树放入栈中

注意：栈是先入后出，后入先出，所以要先放右子树然后放左子树。

第五步：将A的左子树D从栈中取出放入数组，同时获取D的左子树和右子树，因为这里D没有子树，所以直接取出D放入数组

第六步同上：

遍历完成。

是不是看到图的解析之后感觉超级简单，现在上代码：

public static void main(String[] args) { Solution solution = new Solution(); TreeNode t = new TreeNode("F", new TreeNode("B",null,null), new TreeNode("A", new TreeNode("D",null,null), new TreeNode("C",null,null))); System.out.println(solution.preorderTraversal(t));}
public List<String> preorderTraversal(TreeNode root){ if(root==null){ return new ArrayList<>(); }else{ List<String> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()){ TreeNode tmp = stack.pop(); list.add(tmp.val); if(tmp.right!=null) stack.push(tmp.right); if(tmp.left!=null) stack.push(tmp.left); } return list; }}