leetcode-verify-preorder-binary-tree

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/

　　给以一个字符串，判断它是不是一颗二叉树前序遍历序列化的结果。

题目分析

　　先将字符串split成数组，然后利用栈，伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
for(字符串) {
  if(当前字符串不是#) {
    压栈
  } else {
    while(栈不空 && 栈顶为#) {
      弹栈
      栈空直接返回false
      弹栈
    }
    将#压栈
  }
  栈中仅剩一个#，返回true，否则false
}

代码

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) {
        
        Stack<String> stack = new Stack<String>();
        String[] array = preorder.split(",");
        if(array.length == 0) {
            return false;
        }
        for(String s : array) {
            if(!s.equals("#")) {
                stack.push(s);
            } else {
                //s is "#"
                while(!stack.empty() && stack.peek().equals("#")) {
                    stack.pop();
                    if(stack.empty()) {
                        return false;
                    }
                    stack.pop();
                }
                stack.push("#");
            }
        }
        return stack.size() == 1 && stack.peek().equals("#");
    }
}

　　时间复杂度为O(n)