脚本宝典收集整理的这篇文章主要介绍了【非递归实现】二叉树的前中后序遍历,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
//非递归
//根 左 右
class Solution {
public List<Integer> PReorderTraversal(TreeNode root) {
//用数组来存储前序遍历结果
List<Integer> list = new ArrayList<>();
if(root==null) return list;
//创建一个栈
Stack<TreeNode> st = new Stack<>();
//cur指向根节点
TreeNode cur = root;
while(!st.iSEMpty()||cur!=null){
//一边向左遍历,一边将遍历到的节点入栈,节点值入数组
while(cur!=null){
list.add(cur.val);
st.push(cur); //根
cur=cur.left; //左
}
//指针指向栈顶节点(即上一个节点),并将栈顶节点出栈
cur = st.pop();
//指针指向该节点的右子树,开始下一轮的遍历
cur = cur.right; //右
}
return list;
}
}
//非递归
//左 根 右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null) return list;
Stack<TreeNode> st = new Stack<>();
TreeNode cur = root;
while(!st.isEmpty()||cur!=null){
//一边向左遍历,一边将遍历到的节点入栈
while(cur!=null){
st.push(cur);
cur = cur.left; //左
}
cur = st.pop();
//存储遍历结果
list.add(cur.val); //根
cur = cur.right; //右
}
return list;
}
}
前序遍历和中序遍历的代码基本相同,但是后序遍历与它们不太一样
//非递归
//左 右 根
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root==null) return list;
TreeNode cur = root;
//关键在于定义一个cur的前驱节点
TreeNode pre = null;
Stack<TreeNode> st = new Stack<>();
while(cur!=null||!st.isEmpty()){
//一边向左遍历,一边将遍历到的节点入栈
while(cur!=null){
st.push(cur);
cur = cur.left;
}
cur = st.pop();
//若该节点的右节点为空,或者右节点被遍历过,数组才能存储该节点的数值(也就是我们最后才遍历的根)
if(cur.right==null||cur.right==pre){
list.add(cur.val);
pre = cur;
cur=null;
}else{//如果不满足,说明该节点的右节点还没有被遍历过,那么接着向右子节点遍历
st.push(cur);
cur=cur.right;
}
}
return list;
}
}
以上是脚本宝典为你收集整理的【非递归实现】二叉树的前中后序遍历全部内容,希望文章能够帮你解决【非递归实现】二叉树的前中后序遍历所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。