交易所网站开发实战,wap php网站源码,企业建网站 优帮云,安阳文创设计#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ DFS 求解思路 实现代码 运行结果 共勉 题目链接
331. 验证二叉树的前序序列化
⛲ 题目描述
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时我们可以记录下这个节点的值。如果它是一个空节点我们可以使用一个标记值记录例如 #。 例如上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”其中 # 代表一个空节点。
给定一串以逗号分隔的序列验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的
例如它永远不会包含两个连续的逗号比如 “1,3” 。 注意不允许重建树。
示例 1:
输入: preorder “9,3,4,#,#,1,#,#,2,#,6,#,#” 输出: true 示例 2:
输入: preorder “1,#” 输出: false 示例 3:
输入: preorder “9,#,#,1” 输出: false
提示:
1 preorder.length 104 preorder 由以逗号 “” 分隔的 [0,100] 范围内的整数和 “#” 组成 求解思路实现代码运行结果 ⚡ DFS 求解思路
通过递归按照先序来遍历的顺序来遍历二叉树顺序为根-左-右。递归函数的返回值为以当前节点为根的整个树的结束位置递归拿到左子树的结束位置再根据左子树递归返回的位置拿到右子树的结束位置。最后判断为根的整棵树的结束位置是否等于数组中最后一个元素的位置。有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
class Solution {public boolean isValidSerialization(String preorder) {String[] arr preorder.split(,);int index process(arr, 0);return index arr.length - 1 index ! -1;}public int process(String[] arr, int index) {if (index arr.length)return -1;if (arr[index].equals(#))return index;int left process(arr, index 1);if (left -1)return -1;int right process(arr, left 1);return right;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
