当前位置:首页 » 《随便一记》 » 正文

【非递归实现】二叉树的前中后序遍历_m0_52373742的博客

23 人参与  2021年11月06日 13:23  分类 : 《随便一记》  评论

点击全文阅读


二叉树的前中后序遍历

核心思想:用栈来实现对节点的存储。一边遍历,一边将节点入栈,在需要时将节点从栈中取出来并遍历该节点的左子树或者右子树,重复上述过程,当栈为空时,遍历完成。

前序遍历

//非递归
//根 左 右
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;
    }
}

点击全文阅读


本文链接:http://zhangshiyu.com/post/30547.html

遍历  节点  子树  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 大雁南飞人不归结局+番外(沈砚之姜曼殊)结局_(大雁南飞人不归结局+番外大雁南飞人不归结局+番外全书结局)结局列表_笔趣阁(沈砚之姜曼殊)
  • 夕拾难觅朝阳苏亦葵厉晏行完本_夕拾难觅朝阳(苏亦葵厉晏行)
  • [老婆豪掷五百万给初恋,重生后我拒当提款机]人气小说未删减节选_唐欣顾承泽萧然小说节选推荐
  • 半堂花夜渡空城免费在线(裴砚泽沈诺柠)_半堂花夜渡空城免费在线
  • 大雁南飞人不归结局+番外优质全章(姜曼殊沈砚之)_大雁南飞人不归结局+番外优质全章姜曼殊沈砚之
  • [绿茶室友邀请我参加祭祖仪式,却不知我是老祖]人物羁绊章节精选_李岚老祖宗苏婧节选免费试读
  • (番外)+(全书)兰因絮果,爱恨全如玉碎+后续+结局(长乐肖风行)全书在线_兰因絮果,爱恨全如玉碎+后续+结局免费列表_笔趣阁(长乐肖风行)
  • 完结文被绿茶养女夺走真千金身份后,我杀疯了列表_完结文被绿茶养女夺走真千金身份后,我杀疯了(苏楠苏意安+)
  • 刹那芳华顾,褚墨景迟文月+番外+后续_刹那芳华顾,褚墨景迟文月+番外+后续列表
  • 被瘾症折磨的可怜校花免费结局+后续(张团团仁川)全书免费_(张团团仁川)被瘾症折磨的可怜校花免费结局+后续后续(张团团仁川)
  • [竹马率十万铁骑娶我,只为给心上人做嫁衣]反转剧情试读片段_尚书府限免完整章节合集‌
  • 方沐筱宋安(重生后,我将兼挑两房的老公一锅端+后续+结局)结局_(方沐筱宋安重生后,我将兼挑两房的老公一锅端+后续+结局全书结局)结局列表_笔趣阁(方沐筱宋安)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1