首页 > 试题广场 >

遍历二叉树的神级方法

[编程题]遍历二叉树的神级方法

分别按照二叉树先序，中序和后序打印所有的节点。

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

输出三行分别表示二叉树的前序，中序和后序遍历。

示例1

输入

1 2 3
2 1 3
2 3 1

算法知识视频讲解

WYJ96

发表于 2021-07-25 19:08:48

import java.io.;import java.util.; public class Main{ static class Node{ public int value; public Node left; public Node right 展开全文

我要出去乱说

发表于 2022-06-02 12:31:07

1、思路因为遍历二叉树的递归方法实际使用了函数站，非递归的方法使用了申请的栈，两者的额外空间都与树的高度相关，所以空间复杂度为，为二叉树的高度；减少空间复杂度的难点在于从子节点返回父节点，Morris遍历利用了二叉树中大量存在的空闲节点来实现从下层到上层的遍历； Morris遍历原理：展开全文

模拟树

上传者：小小

难度：

8条回答 12收藏 2870浏览

查看代码

扫一扫，把题目装进口袋