首页 > 试题广场 >

已知一棵树的前序遍历是”YOUZANSTyLE”，而中序遍历

[单选题]
已知一棵树的前序遍历是”YOUZANSTyLE”，而中序遍历是”UOZNAYyLTSE”，后序遍历是(    ) 
  • LAyNSTZUEOY
  • UANZOLyTSEY
  • LNyAETZUSOY
  • UNAZOLyTESY
查看答案及解析
添加回答
程序猿Go师傅头像 程序猿Go师傅

首先前序遍历的代码实现如下： 

private void printTree(BinaryTreeNode t){
        if(t!=null){
            System.out.println(t.element);
            printTree(t.left);
            printTree(t.right);
        }
    }

中序遍历代码实现如下： 

private void printTree(BinaryTreeNode t){
        if(t!=null){
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }

图片说明
可以以中序遍历得出的字符串为基础，结合前序遍历得到的字符串来分析整个树是什么样子的。结合图片和步骤树可以理解整个的分析过程。

  1. 整个中序遍历字符串为UOZNAYyLTSE，而前序遍历首个字符为Y，那么根节点必定为Y。由此得出左子树为UOZNA，右子树为yLTSE
  2. 前序遍历第二个字符为O，那么也容易得出，O为root的左子节点，由此得出O的左子树为U，右子树为ZNA
  3. 因O的左子树只有U单个字符，那么O的左子节点必定为U
  4. 已知O的右子树为ZNA，同时前序遍历YOU已经打印完毕，那么开始打印O的右子树的根节点，前序遍历YOU后面紧跟的是Z，那么意味着O的右子节点为Z
  5. 在中序遍历ZNA中，因NA在Z的右侧打印出来，那么NA为Z的右子树，同时前序遍历为AN，那么A为父节点，所以A为Z的右子节点
  6. 中序遍历NA里，A为父节点，那么N是A的左子节点
  7. 同理，右侧子树yLTSE可以用同样的方式分析出结构来，这里就不重复了

编辑于 2019-10-21 21:31:52 回复(0)
菲菲菲12138头像 菲菲菲12138
d
发表于 2023-05-08 16:29:15 回复(0)
小风波～头像 小风波～
D
发表于 2018-12-14 10:14:34 回复(0)
涤生啊头像 涤生啊
D
发表于 2018-12-13 22:28:49 回复(0)
涸辙之鱼201812122013981头像 涸辙之鱼201812122013981
我表示没见过中序遍历

发表于 2018-12-13 21:00:52 回复(0)
提交观点

问题信息

2019 有赞 Java工程师
上传者：小小
难度：
5条回答 4136浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号