题解 | #二叉树的后序遍历#

二叉树的后序遍历

http://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541

  • 后续非递归遍历核心:如果一个节点存在右子树,并且前一个遍历的节点就是右子树节点,才可以遍历当前节点;否则(右子树存在,且没有被遍历),则遍历右子树。
  • 其他部分和前序、中序遍历模板一样。
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();

        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode pre = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.offerLast(cur);
                cur = cur.left;  // 左
            }
            cur = stack.peekLast();
            if(cur.right != null && pre != cur.right){ // 右子树存在,且没有被遍历
                cur = cur.right; // 右
            } else { //右子树已经被遍历
                cur = stack.pollLast(); // 根
                list.add(cur.val);
                pre = cur; // 前一个遍历的节点
                cur = null; // 根已经遍历,置空避免判断内层的while
            }
        }
        
        int[] res = new int[list.size()];
        int i = 0;
        for(Integer val : list){
            res[i++] = val;
        }
        return res;
    }
}












全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务