怎么还有这种题啊，我以为只有想不出来思路和秒过两种题，没想到还有这种堆程序的题。。。看了题解，什么时候我也能写出来这种递归啊，简直美如画😍 class Solution { public: char* Serialize(TreeNode* root) { if (!root) return nullptr; vector<TreeNode*> query; vector<string> rec; query.push_back(root); TreeNode* tmp; ...

这递归太妙了，记录一下 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 ...

说实话，写了这么些关于树的题目，感觉树的题目就应该用递归写，只要思路想清晰，写起来真舒服。这题仔细分析一下就会发现，关键点在于，p和q一定在最近祖先的两侧或本身就是最近祖先。所以就可以自顶向下去找，如果都落在一侧，那这个结点肯定不是最近的祖先，一旦发现落在两侧（包括落在子树的根上），那这个结点就是最近的共同祖先。 class Solution { public: int lowestCommonAncestor(TreeNode* root, int p, int q) { if ((p <= root->val && q >= r...

跟上一题有点类似，如果用两层递归，时间复杂度太大。看了题解才发现可以边递归计算左右子树深度边判断是否平衡。可能平时不怎么用c++，竟然忘了引用这个功能。惭愧惭愧。。。 class Solution { public: bool judge(TreeNode* r, int& depth) { if (!r) return true; int left = 0, right = 0;//左右子树的深度 if (!judge(r->left, left) || !judge(r->rig...

总结一下经验吧，感觉还是要静下心来仔细分析题目，不能急着动笔，不然就会遇到数不尽的坑。练习的时候还可以拿不通过样例调试，实战可没有这种条件。这一题稍微想想就知道可以用层序遍历。通过检查每一层的结点分布以及这一层的层数与个数的关系来判断到该层为止是否是完全二叉树。突然想到其实不用一层一层看，直接将层序遍历当成一个整体看，只要出现过一次None结点，而后面又有非None的结点的时候就可以判断不是完全二叉树。如果一层一层看，就需要多一个判断，判断节点数不满的层是不是最后一层，而整体看就不用考虑这个。 /** * struct TreeNode { * int val; * struct T...

感觉还是有点难度的，我能想到的就三条路：递归。一开始我用递归写了一遍，发现仅仅用自顶向下的逻辑没办法排除下层以下的值比本结点大的情况，所以还得加一个变量去记录每层以各个结点为根的子树的最大值和最小值，如果这个过程也以递归来求，那时间空间成本都太大了，相当于两层循环。栈。虽然这是自底向上的逻辑，但也不好写，首先处理循环中如何不重复放入结点就很麻烦。其次，跟上面说的一样，需要用变量去记录最大最小值，记录的个数应该是2n。费劲巴拉的最后性能不好，得不偿失。转换为链表。因为二叉搜索树按特定规则转换为链表后应该是有序的，所以先转换为链表，再遍历检查就能知道原来的二叉树是否是搜索树。我这里转换代码就用的递...

用广度优先搜索的思路还是很简单的。 class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (!pRoot) return pRoot; vector<TreeNode*> query; query.push_back(pRoot); TreeNode* p, * tmp, * l, * r; while (!query.empty()) { p = query[0]; t...

代码看起来有点繁琐了，主要是结点为None的情况无法放在加法的过程中去考虑，因为这样无法让None指针接收另一个指针的节点值，所以得从none结点的父节点就要考虑none这种情况。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代...

忘记前驱和后继的含义了。。。后面查了才发现自己排反了。 class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if (!pRootOfTree) return pRootOfTree; if (!pRootOfTree->left && !pRootOfTree->right) return pRootOfTree; TreeNode* head = pRootOfTree; TreeNode* lhead =...

递归秒了！不过递归有点太偷懒了，所以又写了一个非递归的。 class Solution { public: int maxDepth(TreeNode* root) { // write code here if (!root)return 0; if (root->left == nullptr && root->right == nullptr) return 1; return 1 + max(maxDepth(root->left), maxDepth(root->rig...

后序遍历：左-右-根。果然还是递归写起来最简单🙂 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param r...

中序遍历：左-根-右 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 ...

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @retu...

坑有点多，不过找到规律也不难。思路很简单，就是python中的split分隔，然后按顺序比较就行。但c++里没这么方便，那就考虑将两个字符串统一格式。我这里就是将两个字符串都变成以'.'结尾的格式，并且将要比较的位数统一，即"1.0"<"1.0.1"=>"1.0.0."<"1.0.1."。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 比较版本号 *...