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

Posted on   |   In   |     |  




From jiuzhang

题目描述

给出一个字符序列，问该序列是否是一棵合法的二叉树的先序遍历？
找到一种不需要构造二叉树的方法。
For example：
“9,3,4,#,#,1,#,#,2,#,6,#,#”
是下面这颗二叉树的先序遍历。其中＃代表空节点。

解题思路

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
  public boolean isValidSerialization(String preorder) {
    String s = preorder;
    boolean flag = true;
    while (s.length() > 1) {
      int index = s.indexOf(",#,#");
      if (index < 0){
        flag = false;
        break;
      }
      int start = index;
      while (start > 0 && s.charAt(start - 1) != ',') {
        start --;
      }
      if (s.charAt(start) == '#') {
        flag = false;
        break;
      }
      s = s.substring(0, start) + s.substring(index + 3);
    }
    if (s.equals("#") && flag)
      return true;
    else
      return false;
  }
}

算法分析

此题可以用暴力搜索解决，但线性复杂度算法也不难想到。写出以上解法，可以达到hire, 而如果用stack解法，则可以 storng hire.

相关练习

树的操作时面试中的高频题目，基础操作（遍历，求深度，求path value等）需熟练掌握。

Verify Preorder Serialization of a Binary Tree

Binary Tree Preorder Traversal

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II

Binary Tree Postorder Traversal (思考非递归算法)

Construct Binary Tree from Inorder and Postorder Traversal