网站运维公司,用html做网站的心得体会,免费用搭建网站,wordpress gif 压缩原题链接 331. 验证二叉树的前序序列化 - 力扣#xff08;LeetCode#xff09; 题目解析 给一个字符串,判断它是否是一个二叉树的前序遍历.不同元素由逗号隔开,空节点用#字符代替.
递归解法 先假设每个元素都由一个字符构成(这样可以先不考虑烦人的多个字符情况) 在接口中调…原题链接 331. 验证二叉树的前序序列化 - 力扣LeetCode 题目解析 给一个字符串,判断它是否是一个二叉树的前序遍历.不同元素由逗号隔开,空节点用#字符代替.
递归解法 先假设每个元素都由一个字符构成(这样可以先不考虑烦人的多个字符情况) 在接口中调用一个递归函数
// preorder 原数组
// pos 下标
// ret 返回值
// tmp 用来简单记录一下递归开始的位置
void fun(string preorder, int pos, bool ret, bool tmp false)
对于preorder[pos]处的递归判断来说
pos下标不合法 ruturnpreorder[pos] # 空节点,不需要再往下执行,直接returnpreorder[pos] 是数字 调用两次fun检测左右子树preorder[pos] , 按照假设这种情况有办法避免,可以不出现,不考虑 运行结束后,在递归执行的入口处如果pos等于数组长度-1,证明成立,否则不成立.
void fun(string preorder, int pos, bool ret, bool tmp false)
{if (pos preorder.size()){ret false;return;}if (preorder[pos] #)return;fun(preorder, pos 2, ret);fun(preorder, pos 2, ret);if (tmp true pos preorder.size() - 1)ret true;}
将多字符元素转化成单子符元素,这个比较简单就不多说了
全部代码
class Solution {
public:void fun(string preorder, int pos, bool ret, bool tmp false){if (pos preorder.size()){ret false;return;}if (preorder[pos] #)return;fun(preorder, pos 2, ret);fun(preorder, pos 2, ret);if (tmp true pos preorder.size() - 1)ret true;}bool fun2(char x){return x 0 x 9;}bool isValidSerialization(string preorder) {bool ret false;int pos 0;string tmp;if (preorder #)return true;char c1 0;for (auto e : preorder){if (fun2(e) fun2(c1))continue;else {tmp.push_back(e);c1 e;}}fun(tmp, pos, ret, true);return ret;}
}; 感谢观看!!!!!
