最开始尝试直接递归原树进行比较，但是思路有问题。退而求其次，直接深拷贝原树，再比较两树。在写比较函数的过程中，我发现之所以最开始原树比较不行，应该是递归函数的比较逻辑出问题了，所以在写完这种方法后继续回头研究原树比较的方法。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { p...

根据中序遍历的规则，可以知道，当该结点有右子树时，返回其右子树最左边的结点。当该结点没有右子树时，则需要向上寻找第一个其左子树中包含该结点的结点。根据这两种需求，分别写两个函数，一个通过递归找最左边的子结点，一个通过递归找向上第一个在左子树中包含该结点的点。根结点由于其next域为空所以需要做特殊处理。 /* struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *right; struct TreeLinkNode *next; TreeLinkNod...

核心思想是递归。首先写一个递归函数来返回树的高度，然后主函数中递归调用该函数比较左右子树的高度。 没有什么特别需要注意的点，就是时间复杂度和空间复杂度有点高。但是也没有想象的那么高。 class Solution { public: bool IsBalanced_Solution(TreeNode* pRoot) { if(!pRoot || (!pRoot->left && !pRoot->right)){ return true; } if(!pRoot->left){ ...

观察容易发现双向链表的顺序与该二叉树中序遍历的结果相同。故首先考虑中序遍历解题。 最开始由于题目中要求空间复杂度为O(1)，故考虑原地操作，但递归的中序遍历也需要用到递归栈，如果真的要满足空间复杂度为O(1)，则需要考虑迭代中序遍历树，或放弃中序遍历的思路。 这里最终还是选择使用中序遍历，将结点按中序遍历的顺序插入数组，然后遍历数组依此修改左右指针。 这里需要注意中序遍历的顺序十分重要，必须是先左子树后右子树，否则就算在遍历数组中反转左右指针，一样会出错。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNo...

深度优先遍历题目的变种。只需要在遍历时多传两个参数，一个用于记录路径和，一个用于记录遍历过的结点即可。 这里有个小坑需要注意，最开始在递归传参时使用了引用传参，导致递归返回后参数不回还原，需要改为值传参。果然引用传参还是存在危险的，需要稍用。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vecto...

刚看到题目尝试使用迭代的方法来找规律逐个元素判断，写到后面发现情况太过复杂，还是递归来的方便。 总体思路是后序遍历的搜索树，其最后一个结点为头结点，而前面的数列则可根据该头结点分为连续的两部分，一部分笔比该结点大，一部分比该结点小。 这样就得到了基本的拆分思路，每次都找到数列最后一个数，然后找到数列中第一个比该数大的数的下标，遍历该下标之后的数，若发现比该数小的，则返回false。否则，继续拆分数列。递归调用函数判断被拆分出来的一大一小两个子数列，并取两个函数的返回值的并作为结果。 上面给出了递归的总体框架，还缺少结束条件，我们发现，只要数列的长度小于3，无论如何它都是一个合理的搜索树，所以结...

二叉树的层序遍历，较为基础。首先用一个二维数组将不同层的结点分开保存，然后将该二维数组的数依次输入到结果数组中即可。遍历过程中使用一个level变量来传递层数信息。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeN...

开始看到题目中说有原地算法，想挑战一下的，但是想了一会没什么思路，还是用常规的遍历解法来做了。 逻辑十分简单，遍历头结点，交换左右子树，再依次遍历左右子树，直到遍历所有结点。 使用递归进行遍历，时间复杂度为O(n)，同时需要维护一个递归栈，空间复杂度为O(n),满足题目要求。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */...

这题的基本思路很简单，难在对于情况的判断。上来看题首先确定题目中要遍历二叉树，并且还需要一个方法来判断是否有相同的结构。注意，这里判断的逻辑与判断两树是否相同基本类似。处理起来就是通过遍历原始树的结点，对每一个结点都调用判断结构的方法，若找到一个结点返回true，则直接返回true。这里说一下判断两个结点是否是相同结构的逻辑，首先若两结点相同，则继续判断其左右结点是否相同，依次重复，直到遍历完给出的子逻辑，返回true，若途中遇到一个结点不同，或原始树先于给出的子结构为空，则返回false。这里的结束判断逻辑有点小坑，想不明白的话容易出错。最开始以为子结构只要出现就会与原始树中直到叶子结点都完...

看题目首先确定采用分治的思想，通过题目给出的先序遍历与中序遍历确定头结点，然后通过该头结点得到两个子树的先序遍历与中序遍历，重复该过程，最后就可以得到完整的树。 具体实现中采用递归的方法，递归的最大栈深度为n，在递归中有一步需要循环来查找头节点，平均时间复杂度为O(logn)，故该方法时间复杂度为O(nlogn),相较于题目要求的O(n)较差，说明仍有改进空间。 空间复杂度方便，仅在递归时借用了辅助栈，故空间复杂度为O(logn)，满足题目要求。 这里有个技巧是通过迭代器来截断vector，这里迭代器的使用并不像直接使用下标，用起来有一些坑需要注意。vector.begin()指向下标为0的元...

由于是二叉搜索树，所以一个结点左边的数都比该结点小，右边的数都比该结点大。 所以可以通过递归，按照中序遍历的顺序，先找到最左边的结点，该结点即为最小结点。然后开始计数，遍历到的第k个结点即为第k小结点。 这样做仅递归遍历了一次链表，大部分情况是不用遍历整个链表的，所以时间复杂度小于等于O(n)。递归过程中需要维护一个栈，空间复杂度等于O(logn)。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ...

基础层序遍历题。在最基本的层序遍历之上增加了隔层逆序的条件。 解题思路是先层序遍历链表，在得到层序遍历好的结果数组后，遍历该数组，遇到偶数层就逆序。 循环最多为一重，时间复杂度为O(n)。递归层序遍历链表时栈深度为n，空间复杂度为O(n)。符合题目要求。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ cla...

递归深度优先遍历计算树深度。 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: int TreeDepth(TreeNode* pRoot) { if(!pRoot){ return 0; } int max = 0; ...

基本思想是遍历链表，当下一个结点的值与本结点相同时，继续查看下一个结点，直到找到一个结点与本结点的值不同，将上一结点的next域指向不同的结点，从而完成将重复结点从链表中去除的需求。 需要注意的是，当列表头结点重复时需要特殊处理。一半的代码都是头结点的特殊处理，有能力的朋友可以尝试优化代码结构。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ...