Leetcode--Java--331. 验证二叉树的前序序列化

本文主要是介绍Leetcode--Java--331. 验证二叉树的前序序列化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在这里插入图片描述

样例描述

在这里插入图片描述

思路

**递归前序遍历 + 模拟 **
核心思路：根据题意进行前序遍历模拟，看模拟过程中是否还有什么问题。
在这里插入图片描述

直接dfs递归前序遍历，按照根左右的顺序。
以“,”作为分隔符进行遍历，首先加上一个“,”，方便处理最后一个。如果dfs中指针k已经越界了，说明没有字符串了，递归中没东西，就是false。否则如果到达空表示这边子树已经走到了空结点，返回true然后切换到另外一边。
最后如果左右子树同时为true才说明能形成树。最后判断k是否恰好在末尾即可（也就是看有没有多余的元素在末尾）。
不用真正地去构造树，只是模拟遍历过程假装形成树。

代码

class Solution {String s;int k;public boolean isValidSerialization(String _s) {//以,作为结束分割，先拼接一个，方便处理末尾的字符s = _s + ',';k = 0;//如果递归dfs中出现问题if (!dfs()) return false;//看是否恰好指向末尾，也就是是否还有多余的元素return k == s.length();}public boolean dfs() {//已经没有字符串了if (k == s.length()) return false;//如果遇到#，就跳过#以及后面的","if (s.charAt(k) == '#') {k += 2;//表示当前分支已经到叶子结点，没问题，可以切换到另外一边return true;}//只要不等于","while (s.charAt(k) != ',') {k ++;}//再跳过","k ++;//上面是对根的处理，下面如果左右子树都没问题，就返回truereturn dfs() && dfs();}
}