写点什么

【LeetCode】验证二叉树的前序序列化 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 03 月 12 日

题目


序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。


例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。


给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。


每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。


你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3" 。


代码


public class DayCode {    public static void main(String[] args) {        String s = "1";        boolean ans = new DayCode().isValidSerialization(s);        System.out.println("ans is " + ans);    }
/** * https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/ * 时间复杂度 O(n) * 空间复杂度 O(n) * @param preorder * @return */ public boolean isValidSerialization(String preorder) { int n = preorder.length(); int i = 0; Deque<Integer> stack = new LinkedList<>(); stack.push(i); while (i < n) { if (stack.isEmpty()) { return false; } if (preorder.charAt(i) == ',') { i++; } else if (preorder.charAt(i) == '#') { int top = stack.pop() - 1; if (top > 0) { stack.push(top); } i++; } else { while (i < n && preorder.charAt(i) != ',') { i++; } int top = stack.pop() - 1; if (top > 0) { stack.push(top); } stack.push(2); } } return stack.isEmpty(); }}
复制代码


总结

  • 这个题目是栈的经典应用,结合二叉树的节点性质,实现的算法。

  • 坚持每日一题,加油!


发布于: 2021 年 03 月 12 日阅读数: 5
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】验证二叉树的前序序列化Java题解