Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

题目描述

给出一个字符序列，问该序列是否是一棵合法的二叉树的先序遍历？ 找到一种不需要构造二叉树的方法。For example：

​​"9,3,4,#,#,1,#,#,2,#,6,#,#"​​ ​​是下面这颗二叉树的先序遍历。其中＃代表空节点。​​

分析解答

通过观察上图中二叉树我们可以发现，一棵合法的二叉树去掉某个叶子节点后仍是合法的二叉树。在给出的字符序列中，叶子节点有很明显的特征，即叶子节点之后一定紧跟两个空节点＃。通过不断的把number,#,#的子串缩成空节点#(把number,#,#子串替换为#)，如果最后字符序列可以缩短到只有一个字符＃，那它就是我们要找的合法的先序遍历了。

参考程序

面试官角度分析

此题可以用暴力搜索解决，但线性复杂度算法也不难想到。笔者认为正确的搜索算法可以达到hire，线性复杂度的算法可以达到strong hire。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。