怎样同时非递归进行二叉树的前、中、后序

实现二叉树先序,中序和后序遍历

http://www.nowcoder.com/questionTerminal/a9fec6c46a684ad5a3abd4e365a9d362

前序和中序可以弄在一个循环里,但是后序我是真不知道怎搞在一个循环里,只能分开写,求大佬指教

import java.util.*;
public class Solution {
    public int[][] threeOrders (TreeNode root) {
        List<Integer> front = new ArrayList<>();
        List<Integer> mid = new ArrayList<>();
        List<Integer> back = backTravel(root);
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        TreeNode last = null;
        // 前序+中序
        while(cur != null || !queue.isEmpty()) {
            if(cur != null) {
                front.add(cur.val);
                queue.push(cur);
                cur = cur.left;
            } else {
                cur = queue.pop();
                mid.add(cur.val);
                cur = cur.right;
            }
        }

        int[][] res = {front.stream().mapToInt(Integer::valueOf).toArray(), 
                       mid.stream().mapToInt(Integer::valueOf).toArray(),
                       back.stream().mapToInt(Integer::valueOf).toArray()};
        return res;
    }
    // 后序遍历
    private List<Integer> backTravel(TreeNode root){
        List<Integer> back = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        TreeNode last = null;
        while(cur != null || !queue.isEmpty()) {
            if(cur != null) {
                queue.push(cur);
                cur = cur.left;
            } else {
                cur = queue.peek();
                if (cur.right == null || cur.right == last) {
                    back.add(cur.val);
                    queue.pop();
                    last = cur;
                    cur = null;
                } else {
                    cur = cur.right;
                }
            }
        }
        return back;
    }
}
全部评论
能直接用递归实现吗?
点赞 回复 分享
发布于 2020-09-08 11:24
好的好的,谢谢大哥。
点赞 回复 分享
发布于 2020-09-08 17:34
我也是后序想了很久,不知道怎么弄到一起……
点赞 回复 分享
发布于 2021-07-17 16:41
左右root = 前序的root左右 => 反转(root右左)
点赞 回复 分享
发布于 2021-12-29 21:38

相关推荐

2024-12-31 09:44
武汉理工大学 Java
程序员牛肉:暑假实习是面向大三招收的哦。你才27届不用急哦。 第一点:在简历的实习板块中简单描述一下你的业务,你说你做了什么什么模块,那你这个模块是在哪个项目中的?简单介绍一下你做的模块所隶属的项目。项目那块挖的还是不够深,先不用着急更新简历,可以再沉淀个四五天。 实习要是让面试官觉得是包装出来的话,是一件很严重的问题,说难听点就是造假。互联网很看重诚信问题,你一旦出现了这种诚信问题,基本这辈子就距离大厂无缘了 2.不要贴任何链接了,没啥用而且很影响美观。有的时候让面试管看着顺不顺眼也是一个是否约你面试的影响因素。
点赞 评论 收藏
分享
白菜小丑呜呜:集美,简历有点问题,+v细嗦
点赞 评论 收藏
分享
评论
4
3
分享
牛客网
牛客企业服务