这个题很重要的一点，null 节点被表示为 # 号，所以每遇到两个连续的 # 时，就表示这是一个叶子节点。
这个时候就需要用栈来进行维护，当遇到连续两个 #，就将这两个 # 弹出，并弹出这个叶子节点，随后再 push 一个 #，表示这个点已经被删掉。
如样例
9 3 4 # # 1 # # 2 # 6 # #
9 3 #
9 3 # # => 9 #
9 # 2 # # => 9 # # => #
class Solution { public: bool isValidSerialization(const string &preorder) { vector<string> preOrder; for (int i = 0; i < preorder.size(); ++i) { int j = i + 1; while (j < preorder.size() && preorder[j] != ‘,‘) ++j; preOrder.emplace_back(std::move(preorder.substr(i, j - i))); i = j; } stack<string> stk; for (int i = 0; i < preOrder.size(); ++i) { if (!push(stk, preOrder[i])) return false; } return stk.size() == 1 && stk.top()[0] == ‘#‘; } private: bool push(stack<string> &stk, const string &s) { if (s[0] != ‘#‘) { stk.push(s); return true; } if (stk.empty() || stk.top()[0] != ‘#‘) { stk.push(s); return true; } stk.pop(); if (stk.empty() || stk.top()[0] == ‘#‘) return false; stk.pop(); push(stk, "#"); return true; } };
入度出度：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/solution/pai-an-jiao-jue-de-liang-chong-jie-fa-zh-66nt/
原文：https://www.cnblogs.com/rookie-acmer/p/15208399.html