我的博客主页 |
非递归遍历二叉树
- 前序遍历(迭代)
- 中序遍历(迭代)
- 后续遍历(迭代)
二叉树的遍历方式有:前序遍历、中序遍历、后续遍历,层序遍历,而树的大部分情况下都是通过递归的方式来进行的。
首先要明白递归是函数自身调用自身,设计了很多因素记录树中遍历的入栈 记录地址等。。。因为是在栈上开辟空间,这些操作对于时间和空间的消耗会更大,且容易溢出。迭代(非递归)它是在栈堆中开辟更大的空间,不容易溢出,且不会调用函数自身,效率也会提升很多。
更多的二叉树的oj题目在我的专栏中,感谢大家的观看
在数据结构中的学习难免少不了递归的学习,递归有时候也会让代码变得更加简洁,学习递归让我们对代码有更近一步的思考。
前序遍历(迭代)
每遍历一个节点打印一次元素且将其放入栈中,直到为空时,将栈顶元素移除来并打印并让其查看另一子树是否为空节点。
public static void preOrderIteration(TreeNode root){if(root==null)return ;//根节点没有属性Stack<TreeNode> stack=new Stack<>();TreeNode cur=root;while(cur!=null||!stack.isEmpty()){while(cur!=null){stack.push(cur);System.out.print(cur.val+" ");cur=cur.left;}cur=stack.pop();//将从栈中弹出的元素给到curcur=cur.right;//cur的右边赋值给cur是否为空}}
中序遍历(迭代)
因为中序遍历是左根右,给定一个辅助栈,每次走到最后一个节点的left或者right为空时将栈中的元素给到数组,然后再去遍历栈顶右边元素是否为空。
public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();Stack<TreeNode> stack=new Stack<>();while(root!=null||!stack.isEmpty()){if(root!=null){stack.push(root);root=root.left;}else{//如果为null说明该节点的左子树为空,将栈顶元素放入数组中list.add(stack.peek().val);//检查栈顶的右节点root = stack.pop().right;}}return list;}
后续遍历(迭代)
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list=new LinkedList<>();if(root==null)return list;Stack<TreeNode> stack=new Stack<>();TreeNode prev=null;//记录上一个移除栈的元素while(root!=null||!stack.isEmpty()){while(root!=null){stack.push(root);root=root.left;}TreeNode top = stack.peek();//查看顶部元素右树是否为空//两个条件,右树为null或者此元素右树已经出过栈则直接出栈if(top.right==null||prev==top.right){TreeNode cur = stack.pop();list.add(cur.val);prev=top;//记录上一个栈顶元素}else{root=top.right;}}return list;}