LeetCode 331 - Verify Preorder Serialization of a Binary Tree

作者 QIFAN 日期 2016-12-21
LeetCode 331 - Verify Preorder Serialization of a Binary Tree

原题链接:331. Verify Preorder Serialization of a Binary Tree


题目

给一串字符串,代表一棵树的先序遍历结果,节点间用 “,” 隔开,“#” 代表叶节点。在不重建树的情况下,判断该字符串能否成树。

假设如下一棵树,其先序遍历结果为 “9,3,4,#,#,1,#,#,2,#,6,#,#” 。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

举例 1 :
“9,3,4,#,#,1,#,#,2,#,6,#,#”
返回 true

举例 2:
“1,#”
返回 false

举例 3:
“9,#,#,1”
返回 false

思路

拿到这题我有点懵逼,看了十分钟没有想出思路。就直接去看答案了。

思路 1 流入流出

把树看成一颗网络图。将从父节点来的作为输入( in ),到子节点去的作为输出( out )。所以对于除根节点外的非叶节点,有 2 个输出,1 个输入,净输出 1 个;对于叶节点(“#”),则只有 2 个输入。根据树的结构,叶节点的个数比其他节点的个数多 1 ,也就是说,输入的次数比输出的次数多 1 。另外考虑到由于是先序,所以首先会经过父节点(至少一个父节点),也就是说在整个遍历过程中,叶节点的累积数量最多会比其他节点的累积数量多 1 。
因此,只要考虑两种条件:

  1. 输出数量始终比输入数量小 1
  2. 结束时输出的数量比输入数量小 1

我可以知道如果是一颗树的先序遍历,那肯定能满足这两个条件,但是不明白为什么逆命题也是对的。

代码:

public class Solution {
public boolean isValidSerialization(String preorder) {
int in = 0;
int out = 1;
String[] nodes = preorder.split(",");
for (int i = 0; i < nodes.length; i++) {
if (out <= in) return false;
if (!nodes[i].equals("#")) {
out += 2;
}
in++;
}
return in == out;
}
}

这是目前最简洁的方法。时间复杂度为 $O(n)$ ,空间复杂度为 $O(1)$

思路 2 stack

从左往右遍历节点

  1. 如果碰到数字,则放入栈
  2. 如果是 “#” ,则看栈顶是不是 “#”
    1) 如果是 “#” , 则一直 pop 直到栈顶不是 “#” 或者栈为空
    2) 如果不是 “#”,则直接放入栈

最后看栈中是不是只有一个元素且为 “#”

这个方法的原理是:
case 1:如果碰到数字,说明这是一个父节点,按照先序遍历的规则,说明他的子树还没遍历,就直接放入栈。
case 2:如果是 “#”
case 2.1:如果栈顶不是 “#” ,说明这是左孩子,所以直接放进栈中作为后面的一个标记
case 2.2:如果栈顶是 “#” ,说明这是右孩子,说明这颗子树已经遍历完整。先推出左孩子,
case 2.2.1:若栈为空了,说明这串字符无法成树,不然一定还有一个父节点在栈中。
case 2.2.2:栈不为空,继续推出栈顶的父节点。继续循环 case 2

代码(来源 leetcode@yanggao):

public class Solution {
public boolean isValidSerialization(String preorder) {
// using a stack, scan left to right
// case 1: we see a number, just push it to the stack
// case 2: we see #, check if the top of stack is also #
// if so, pop #, pop the number in a while loop, until top of stack is not #
// if not, push it to stack
// in the end, check if stack size is 1, and stack top is #
if (preorder == null) {
return false;
}
Stack<String> st = new Stack<>();
String[] strs = preorder.split(",");
for (int pos = 0; pos < strs.length; pos++) {
String curr = strs[pos];
while (curr.equals("#") && !st.isEmpty() && st.peek().equals(curr)) {
st.pop();
if (st.isEmpty()) {
return false;
}
st.pop();
}
st.push(curr);
}
return st.size() == 1 && st.peek().equals("#");
}
}

该方法时间复杂度 $O(n)$ ,空间复杂度为 $O(n)$