二叉树的递归和非递归遍历,树的先根遍历相当于二叉树的

wmdbm顺利地通过树递归解决了问题。 面试官说递归太简单了。 你能写一个迭代版本吗？

此时是用数据结构模拟jvm构建的堆栈的时候了。

二叉树的前序扫描() ) ) ) ) ) ) ) ) ) )。

想法1 :递归

类解决方案{ publiclistintegerpreordertraversal (treenode root ) { ListInteger res=new LinkedList )； if (根==空)返回RES； RES.add (根. val )； RES.addall (前序遍历)根. left )； RES.addall (前序遍历) root.right )； 返回RES； (构想2 )反复

将递归转换为非递归的一种常见方法是手动模拟和维护堆栈。

对于递归，jvm隐式维护堆栈，但对于迭代，必须显式模拟堆栈。

将整棵树最左边的链推入堆栈，推入堆栈顶部，同时向res链表中添加元素，每次取出堆栈顶部的元素时判断是否有右边的子树

如果有右部分树，则将以右部分树为根节点的左部分树推入堆栈中，记录到结果res中。 然后再次取出堆栈顶部的元素，判断是否有右边的子树，如果没有右边的子树，则继续弹出堆栈(

循环结束的条件是当前指针不为空或堆栈不为空的class solution { publiclistintegerpreordertraversal (treenode root ) { list integer RES if (根==空)返回RES； dequetreenodestack=new linked list (； wile (路线！=空| |！ stack.isEmpty () /当前节点的左分支while (根！=空值(RES.add ) root.val )； stack.push (根)； 根=根.左； (if (！ stack.isEmpty () ({ TreeNode temp=stack.pop )； root=temp.right； } }返回RES； }二叉树的中顺扫描()。

想法一：递归写作

类解决方案{ publiclistintegerinordertraversal (treenode root ) { ListInteger res=new LinkedList )； if (根==空)返回RES； //首先是左边的子树RES.addall(inordertraversal ) root.left )； //添加根RES.add(root.val )//右边的子树RES.addall(inordertraversal ) root.right )； 返回RES； }} 思路二：迭代写法

由于采用了反复的写法，所以不断调用内存堆栈，不使用递归的方式。 那么，自己模拟写堆栈，进行进入堆栈的操作和退出堆栈的操作。自定义栈的方式来模拟迭代的写法非常常见，一定要掌握!

将整棵树的最左边的链推入堆栈，每次取出堆栈的最上面的元素时添加到结果集中，判断是否有右边的子树

如果有右边的子树，则将右边的子树作为根节点的左边的子树推入堆栈。 然后，再次检索堆栈顶部的元素，添加结果集，并确定是否有右边的树。 (循环了)如果没有右边的树，继续弹出堆栈

循环结束的条件是代码中写入了当前指向不为空或堆栈不为空的逻辑。 我觉得还有点罕见，转换时仔细想想

class解决方案{ publiclistintegerinordertraversal (treenode root ) { ListInteger list=new LinkedList )； dequetreenodestack=new linked list (； wile(r

oot != null || stack.size() != 0){ while(root != null){ stack.push(root); root = root.left; } //将当前的根加入list 同时判断是否有右结点 TreeNode temp = stack.pop(); list.add(temp.val); if(temp.right != null){ root = temp.right; } } return list; }} 二叉树的后序遍历 （※）

思路一：递归

class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> res = new LinkedList<>(); if(root == null) return res; res.addAll(postorderTraversal(root.left)); res.addAll(postorderTraversal(root.right)); res.add(root.val); return res; }}

思路二：迭代

手动构建一个栈，对这颗树进行前序遍历，将前序遍历的结果压栈，之后对栈顶的结点进行判断。

该节点没有右子树 那么这个结点就是根节点了，可以直接添加该节点有右子树，需要先去添加它的右子树。让指针指向它的右子树，然后在对他的右子树进行前序遍历压栈，取栈顶，判断这样的循环的操作。

当前元素加入res 的标准是 当前结点的右子树为空 || 当前结点的右子树已经添加到结果集了。

但是这里面有一个坑就是要记录当前节点的右子树是否添加过的状态

所以解决的办法就是：只要有元素添加到list 中 ，就记录这个结点，就表明这以这个结点为根的子树都已经添加过了。
下次对某一个结点的右子树进行添加的时候，判断一下右节点是不是刚刚加入过list中即可。

class Solution { public List<Integer> postorderTraversal(TreeNode root) { Deque<TreeNode> stack = new LinkedList<>(); List<Integer>list = new LinkedList<>(); TreeNode prev = null;//prev 用来指向以当前结点为根节点的子树已经添加过了 while(root != null || stack.size() != 0){ //进行前序遍历放所有的左子树 while(root != null ){ stack.push(root); root = root.left; } TreeNode temp = stack.peek(); if(temp.right != null && temp.right != prev){ //当前的结点是有右子树的 并且没有添加过 root = temp.right; }else{ //出栈 同时进行标记 添加的元素 list.add(stack.pop().val); prev = temp;//这里进行标记 list 最近一次添加的元素 表示以当前结点的为根的子树都添加过了 } } return list; }} 二叉树的层序遍历

思路一：
借助队列的方式 拖动结点的左右孩子。
不断的新建临时的list，但是通过循环控制list里面添加的数量。
堆列没有拖动孩子之前队列中的元素的个数 就是当前的temp 中的个数！

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return res; queue.add(root); while(!queue.isEmpty()){ List<Integer> temp = new LinkedList<>(); int size = queue.size();//获得没有拖动孩子时候的队列个数 //控制当前的temp 里面添加的元素个数 for(int i = 0; i<size;i++){ TreeNode node = queue.remove(); temp.add(node.val); if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } } res.add(temp); } return res; }}

思路二：带结点数字的的层序遍历

判断当前结点的序号 是不是已经等于res列表中的size个数 如果等于就新建立一个temp。
当开始 第零层 res 的size是0 相等 创立一个temp ，并加入list 它的左右孩子就是 第一层

遍历到第一层的第一个元素时 res 的size 是1 当前的level 也是1 于是在res中创建第二个temp 并加入当前元素。
遍历到第一层的第二个元素时 res的size是 2 当前的level 是1 于是拿出最后最后一个temp 加入。

遍历到第二层第一个元素时 res 的size 是2 当前的level 也是2 于是在res中创建第三个temp 并加入当前元素。
遍历到第二层的第二个元素时 res的size是 3 当前的level 是2 于是拿出最后最后一个temp 加入。
…

class Solution { //自定义了一个带层级的类 //这个val表示的是当前遍历的是第几层 class NT{ TreeNode node; int val; public NT(TreeNode node, int val) { this.node = node; this.val = val; } } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); //建立一个队列辅助完成二叉树的层序遍历 Queue<NT> queue = new LinkedList<>(); if(root == null) return res; queue.add(new NT(root,0)); while(!queue.isEmpty()){ NT cur = queue.poll(); int level = cur.val; TreeNode node = cur.node; if(level == res.size()){ //在总的结果中添加list res.add(new ArrayList<>()); } //拿到对应的内层的list List<Integer> innerList = res.get(level); innerList.add(node.val); //把它的两个孩子拖动进来 if(node.left != null){ queue.add(new NT(node.left,level+1)); } if(node.right != null){ queue.add(new NT(node.right,level+1)); } } return res; }}