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

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

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;
    }
}
全部评论
左右root = 前序的root左右 => 反转(root右左)
点赞 回复 分享
发布于 2021-12-29 21:38
我也是后序想了很久,不知道怎么弄到一起……
点赞 回复 分享
发布于 2021-07-17 16:41
好的好的,谢谢大哥。
点赞 回复 分享
发布于 2020-09-08 17:34
能直接用递归实现吗?
点赞 回复 分享
发布于 2020-09-08 11:24

相关推荐

05-25 10:45
西华大学 Java
Frank_zhang:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
点赞 评论 收藏
分享
评论
4
3
分享

创作者周榜

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