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

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

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

相关推荐

12-05 15:53
中南大学 Java
点赞 评论 收藏
分享
上海拼多多 算法工程师 总包54(好像是多多的算法白菜价 [笑cry]?)
sunrrrrise:多多太低了
点赞 评论 收藏
分享
评论
4
3
分享
牛客网
牛客企业服务