所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

树的题目，首先考虑树为空的特殊处理。树的题目类型大概有：

树的遍历

前序、中序、后序、层序等。
树的构造

构造树、合并树等。
树的特殊结点查找

找前驱后继等
树的路径

路径分为可以有兄弟结点和不可以有兄弟结点的路径，只要是路径题目，就考虑路径的开头和结尾，并考虑以具体结点为开头或者结尾的情况有多少种，以便计算时间复杂度。二叉树的一个特点：从叶子结点到根结点有且只有一条路径。
几个类似的等价的解法的题目

中序搜索二叉树，求二叉树的中序后继、前驱，删除二叉树的结点，设计二叉树的中序迭代器。

具体题目

144. Binary Tree Preorder Traversal

题意：前序遍历二叉树。

解：递归解法：先遍历根元素，接下来就是递归到左右子树的递归。

非递归解法：遍历的意思，就是可以把该元素打印出来。问题难点在于，先要打印完左孩子，才能打印右孩子，先遍历左孩子后当前结点会丢失，需要使用数据结构保存。使用什么结构呢？由于树是一种递归型的结构，遍历左孩子的过程中，左孩子对自己的左孩子也有相同的处理方式，所以使用栈，每次访问到的结点都是作为栈顶，虽然后来但是先处理。

方法一：从root开始，在该节点不为空或者栈不为空的时候，进行遍历：首先不断向左访问直到最左边的孩子，访问过程中的结点全部压栈，直到最左边的孩子后，意味着左侧的孩子全部打印了，此时应该处理栈顶元素了，弹出一个元素（如果栈不为空）那么同样逻辑（访问所有左孩子）处理该元素的右孩子，然后继续进行栈处理。

方法二：把元素的访问和打印操作分开，访问意味着要进行当前结点的打印以及处理他的左右孩子，例如，一开始就是对root进行访问，对root进行访问后栈状态是：{访问root的右孩子，访问root的左孩子，打印root}。

http://blog.csdn.net/gatieme/article/details/51163010

94. Binary Tree Inorder Traversal

题意：中序遍历二叉树。

解：递归解法：空结点直接返回，只有一个结点，那么就直接打印，否则，先解决左孩子的子问题，然后打印自己，再解决右孩子的子问题。

非递归解法，方法一：访问左孩子的时候，不进行打印就进行入栈操作，所有左孩子压栈后，打印栈顶结点，然后对栈顶结点的右孩子做相同处理。

方法二：把元素的访问和打印操作分开，一开始就是对root进行访问，对root进行访问后栈状态是：{访问root的右孩子，打印root，访问root的左孩子}。

145. Binary Tree Postorder Traversal

题意：后序遍历二叉树。

解：递归解法：空结点直接返回，只有一个结点，那么就直接打印，否则，先解决左孩子的子问题，然后解决右孩子的子问题，最后打印自己。

非递归解法：方法一：修改先序遍历的程序。先序遍历是根－左－右，后序遍历是左－右－根。只需要将先序遍历的程序改为根－右－左，然后只需要反转，就可以得到左－右－根。

方法二：也需要先把左孩子全部入栈，问题是打印结点的时机：打印完右子树才能打印根，也就是说，对栈顶的处理是对栈顶的右孩子做相似的处理（此时不弹栈顶），但是存在另外一种情况是，有时候栈顶需要弹出来，例如遇到了基本情况发现栈顶元素没有左右孩子，或者是最后一次打印的元素是栈顶元素的右孩子。那么，对于栈顶处理的分辨技巧就是使用变量记录下最后一个被打印的点：弹栈的时候对于其右结点进行判断，如果右结点为空，或者右结点是上一次打印过的结点，那么栈顶要被打印，且栈顶的右孩子不再做同样处理了，因为已经处理过了：栈顶打印之后，一个是要更新最后打印的结点为栈顶，另一个是要把当前cur元素置nullptr表示以后不需要考虑cur的左孩子压栈的问题。如果两个条件都不符合，那么直接对栈顶右孩子进行同样的处理。

小结：后序遍历的特点就是：右孩子一旦要打印，那么下一个打印结点只能是他的父节点。

方法三：把元素的访问和打印操作分开，访问意味着要进行当前结点的打印以及处理他的左右孩子，例如，一开始就是对root进行访问，对root进行访问后栈状态是：{打印root，访问root的右孩子，访问root的左孩子}。

687. Longest Univalue Path

题意：找出二叉树中相同数字最长链的长度。最长链可以经过父节点到兄弟结点。

解：分治法。将以root为根的子树的问题记作f，解决问题的过程是f(root)，答案也是f(root)。对于f(root)，分为两种情况，一种是root不在最长链里面(这个问题记作g)，一种是root在最长链里面(记作f)。所以有f(root) = max { g(root), h(root) }。

先来看最长链不经过root的情况：答案是在root的左子树或者右子树的子问题之中的较大者，也就是有：g(root) = max{ f(root.left), f(root.right) }

在看最长链经过root的情况：这种情况继续分解为三种情况：

第一种：最长链经过root以及root的左子树且右子树；第二种：最长链经过root，以及root的左子树或右子树中的一个；第三种：最长链只有root自己。

来看第一种情况，如果我们把这个问题记为j(root)，那么发现是无法得出j(root)的递推公式的，因为这个问题并不是一个递归问题（或者说是分治问题），理由是例如j(root.left)，它也是经过自己的左右孩子，那么和父节点root经过它的情况相矛盾。

在看第二种情况，这个问题记为k(root)，可以知道k(root)的递推公式：k(root) = 1 + max {k(root.left), k(root.right)}; 在看第三种情况，这种情况下答案是0（链的长度指的指边的数量，不是点的数量）。

再来重新考虑第一种情况，这种情况下，由于第二种情况可解，那么第一种情况的解公式（不是递推公式）为:j(root) = 2 + k(root.left) + k(root.right)

总结下来，得出h(root)的简化公式：h(root) = max { 1 + max {k(root.left), k(root.right)}, 2 + k(root.left) + k(root.right) } }

总体来说，f(root)并不是一个递归的公式，因此需要进一步的找规律进行化简。发现g(root) = max{ f(root.left), f(root.right) }其中的 f(root.left)可以考虑用k函数来进行替换，但是此题并不是进行数学推导。。实际上，我们需要的套路就是一个全局的递归遍历，在自下而上的过程中，每个节点要告诉上一层的节点，该节点计算出的一些关键的信息，例如：经过此节点的k函数的结果， j函数的结果。也就是说，重要的是分之后的合并过程，也就是基本情况给父节点提供信息。

编码考虑的思路：每个点考虑基本情况，一个是要提供自己单连左子树或右子树的较大者给父节点做参考，另一种是考虑自己可以把左右子树全链接起来作为整体结果的一个候选者。

235. Lowest Common Ancestor of a Binary Search Tree

题意：求搜索二叉树中两个点p和q的最低公共祖先。

解：从root开始，如果当前访问结点大小如果介于p和q之间，直接返回，如果比两者都大，那么问题递归到左子树，如果比两者都小，就递归到右子树。

此题的启发：（1）对于树的问题，一定要看清是什么树，对于特殊的例如搜索二叉树，那么就要使用特殊的搜索方法。

（2）要考虑结果的性质，也就是看结果会落入哪些情况。此题，如果经过细心观察，可以发现，如果树上的一个结点大小介于p和q之间，那么他必定就是最低公共祖先。

PS.此题技巧是不用关心p和q谁大，只需要知道root是不是比两个都大或都小，然后剩下的就直接返回root就行了。

236. Lowest Common Ancestor of a Binary Tree

题意：此题和235题不一样之处在于，是一棵普通的二叉树。

解：如果pq两个结点分别处于某结点为根的树的两侧，那么该结点就是最低公共祖先。这一点比较难想到。

分治法解决，首先考虑分解，看根，如果根是p或者q，那么作为答案返回，否则根的结果应该是与自己的左子树的lca的答案一致，或者是与右子树的lca的答案一致，其中如果左右子树的lca分别是p和q，那么说明根自己是答案。

在来考虑基本情况：（1）树为空，返回空作为lca答案；

（2）树只有一个节点，如果该节点是p或q，则返回p或q作为lca答案，否则返回空作为lca答案；

（3）树有两个或三个节点，如果根是p或q，那么p或q就是lca结果；如果根不是，那么看子节点，也就是递归到情况1和2，也就是说，子树的lca答案一定要发给父结点做参考。

总结：根是答案有两种情况：（1）根是p或者是q，（2）pq的位置位于根的两侧。在当前树中，如果先找到p，那么就直接返回p，如果先找到q，那就直接返回q。对于root，只存在如下情况：一个是p或q和root相等，那么直接返回作为结果就行了；另一个是root和p，q都不等，那么问题递归为左子树中找和右子树中找，如果两个都找到了，说明p和q是在root的两侧，那么返回root。否则，找不到的为空，返回其中一个找到的就可以了。

PS. 所谓递归，就是先将大问题变为子问题，然后将分解过程形成一种逻辑上的结构，这种结构适合放在数据结构栈里面，直到遇到基本情况的时候，这种结构开始消解，结构为空的时候自然得出答案。也就是说，无需关心栈具体长什么样，而是只要相信栈结束后就能得到要求的解就行，而且要知道的就是，时间看起来是比N变多了的，但是有的时候并不影响复杂度的量级，而是要根据公式来具体计算。对于本题，递归公式为 T（n）＝ 2 T(n / 2) + O(1)，根据画分治的树或者数学递推式计算就可以知道， T（n）＝ 1 ＋ 2 ＋ 4 ＋ … ＋ n，根据等比公式，结果为 2n －1，也就是时间复杂度是O(n)。对于递归，真正要关心的就是基本情况以及如何对问题进行分解。

总结：一个父结点解决不了的问题，就交给子结点去解决，但是子结点的答案只能作为父结点的参考；与此同时，父结点还要将自己的答案交给它的父结点去参考。

617. Merge Two Binary Trees

题意：是merge两个二叉树。

解：递归，先合并自己，然后递归合并左右子树。

启发：看到树的题目，首先想能不能递归解决，能的话，就考虑递归的出口，也就是假设子树已经解决了问题了，接下来看自己如何解决。

606. Construct String from Binary Tree

题意：是先序的遍历树，把遍历的路径构建特殊字符串：把左右子树用括号分别扩起来。

解：递归的先序，其他不要想的太多。树的问题，第一反应就是能否递归解决。

注意：如果右孩子结点不为空，而左孩子结点为空时候，需要加入多余的”()”。

536. Construct Binary Tree from String

题意：由606题生成的串还原回原来的树。

解：递归。分析下当前字符串，发现字符串格式为rootVal＋（左子树）＋（右子树）。所以现在需要一个变量cnt来记录左括号的数量（类似括号匹配时候的处理），遇到左括号，cnt＋1，遇到右括号，cnt－1。先把rootVal部分找到，然后向后找，如果cnt为0，说明是左孩子或者是右孩子，这时候需要保存第一个左括号的起始位置，在处理完左子树之后，将标记移动到第二个左括号的起始位置，就可以分辨出右子树。也就是说，同时处理左右孩子，就可以区分开左右孩子。

98. Validate Binary Search Tree

题意：验证一棵二叉树是不是二叉搜索树。

解：二叉搜索树意味着左右子树是二叉树，且左子树始终小于根，小于右子树。

方法一：使用二叉搜索树的性质，中序遍历是有序的，进行一次中序遍历，遍历时候，记录前一步的值，如果下一个访问的值比前一步的值小或等于，那么说明不是二叉搜索树。 prev值初始化为INT64_MIN。

使用递归遍历的时候，其实可以计算每个点为根的二叉树是不是搜索树，它的左右子树均为二叉搜索树是必要条件。

方法二：进行前序遍历，如果是二叉搜索树，那么当前处理值对左右子树来说，意味着：（1）它比所有左子树的值大；（2）它比所有右子树的值小。

这样，进行前序遍历，如果所有的点都满足落入当前的最大值最小值范围内，那么就符合二叉搜索树的要求。一开始的最小值是INT64_MIN,最大值是INT64_MAX。

方法三：使用后序遍历，每个点扫描的时候，要看是不是比左子树的最大值大以及比右子树的最小值小。每次结点的计算，都要返回当前结点为根子树的最小值，最大值以及当前子树是否是BST，递归的基本情况是：空节点的最小值为INT64_MIN,最大值是INT64_MAX。一个点如果满足条件之后，要对结点的最小最大值进行更新，也就是左子树的最小值和右子树的最大值，有例外就是左右子树为空的时候，最小（大）值要更新为结点的值。

501. Find Mode in Binary Search Tree

题意：找出BST中的所有众数。

解：如果是普通遍历，加hash表，那么相当于是O(n)时间、空间，但是没有使用到BST的性质。利用BST性质进行中序遍历，我们知道可以从小到大依次遍历，所以使用中序遍历，每次遍历的值看等不等于prev，如果相等，那么当前值的数量统计cnt加1，然后看cnt是不是比最大cnt大，如果大的话，那么把结果数组清空，如果等于最大cnt，那么加入结果数组。

449.Serialize and Deserialize BST

题意：序列化BST

解：序列化的要点：序列化的信息需要保证是二叉树的一种唯一表达的形式。需要深刻理解二叉树的唯一形式，也就是二叉树的空节点信息不能忽略，而要看作“#”，而且要注意一点，就是唯一的表达形式，其中节点之间要由字符（例如空格，逗号）隔开！例如元素11和1，如果不隔开，那么结果为111，1和11也是111。

此外，此题区别于297题在于，需要充分利用BST的特点，也就是比所有左孩子大，比所有右孩子小。因此，全搬297的解法，虽可行但不是最优的。

可以对297的方法一进行改进（解法时间总体复杂度不会变化，而空间复杂度可以减小）。

和297方法一不同之处在于：二叉树的形式可以使用先序遍历＋中序遍历（默认就有，无需记录）来唯一表达。也就是说，序列中无需记录“#”空节点，而只需要记录先序遍历结果（更加简短）。

中序遍历结果（就是升序）是已知的，可以在树还原（反序列化）过程中可以加以利用。具体解法是，例如先序序列是3，1，2，4。根据先序数组遍历，一个个的看，第一个元素3必为根元素，原因是先序的第一个元素，之后第一个元素把整个解空间（LONG_MIN, LONG_MAX）切分成两个部分：（LONG_MIN, 3）和（3, LONG_MAX）且分别对应于3的左子树和右子树的解空间。此时在看第二个元素1，首先作为左子树考虑，由于1在（LONG_MIN, 3）区间内，所以合格，那么1作为3的左孩子存在；在看元素2，由于是先序，那么优先考虑2能不能作为元素1的左孩子或者右孩子，而我们知道1的左孩子的解空间是(LONG_MIN, 1)，1的右孩子解空间是（1， 3），所以2只能作为1的右孩子存在，依次类推。

编码时候保持一个当前节点所属的最大值和最小值，如果当前扫描的先序值不介于函数规定的最大最小值之间，说明该结点不属于该子树，直接返回空结点，否则创建该结点，然后进一步定义它的左右子树的最大最小值，左子树的最大值更新为当前节点的值（比父节点小），最小值和当前最小值一致，右子树最小值修改为当前节点的值，最大值和当前最大值一致。

PS. (1) int与string，char型之间的转换技巧 int转string，例如：123转成“123”，使用to_string（123）。 string转int，例如将123转“123”，使用stoi（“123”）。 char＊转int，例如char *c = ‘1’转1，使用atoi（c），如果是string数组的下标访问形式，那么要加.c_str()，例如：atoi(s[8].c_str())。 char转int，例如‘1’转1, 直接使用’1’ - ‘0’即可，对于string数组的下标访问形式也是一样，例如s[8] - ‘0’。

(2) c++的split，参考https://github.com/jingminglake/Practice/blob/master/split/split.cpp

662. Maximum Width of Binary Tree

题意：求树中最远的两个结点，从横向距离（宽）来看。

解：是带层次的宽搜，要注意的是，将树当作满树结构来看，也就是说，每个结点其实都是可以按满树进行编码的。入队的时候，要加入结点的编码信息，左孩子是2i, 右孩子是 2i+1。

层次宽搜，每次把该层第一个元素的下标取出来，然后扫描的时候，把该层最右边的下标也取出来，然后就能知道当前层的宽度。

此题编码时候要注意的：1. 下标的类型不能为int，否则越界

right - left的时候，要在每一层结束时候减去，如果在层内处理时候减，那么可能出现right没有赋值，却去减left的情况，也就是right是0，而left是正的情况。

545. Boundary of Binary Tree

题意：求树的逆时针边界组成的数组，即［左边界、叶子、右边界］。

解：一种解题思路：先理解左右边界：左边界就是除了叶子结点以外的最左边的路径，也就是有左孩子且左孩子不为叶子的时候就向左走，并沿途记下结点，然后如果没有左孩子，那么向右孩子走，如果右孩子不是叶子，则记下来，然后沿着右孩子的左孩子走。也就是一个遇到叶子结点就停止的一直沿着最左边走的过程。

同理，右边界是一个遇到叶子结点就停止的一直沿着最右边走的过程。

叶子结点可以使用先序遍历来找。

所以，只需要三遍扫描就可以得出答案。注意的是一开始的root为非叶子时候，一开始就要加入结果中，然后在找左边界右边界的过程中，只需要处理左右孩子即可，这样root就不会重复算。而root作为叶子时候，不需要先加入，因为后面处理叶子时候，会从root开始算。

270. Closest Binary Search Tree Value

题意：求二叉搜索树中离target最近的结点的值。

解：解题的关键在于理解如果target比root值大，那么root的左子树不用在考虑了，因为root肯定比左子树大，target又比root大，所以结果肯定是root或者是root的右子树中。反之亦然。

非递归解法：使用循环进行二叉树搜索，root值比target大的时候，向右边搜索，反之，向左搜索。然后沿途更新离target最近的值，最终搜索到空结点的时候，返回最近的值。

递归解法：root值比target大的时候，结果在自己和右子树子问题求出的结果中离target最近的那个，反之亦然。难点是递归时候，在树为空的时候，该如何返回。方法是自己定义helper函数，在空的时候，返回int64的最大值。

101. Symmetric Tree

题意：验证二叉树是不是对称的。

解：二叉树是对称的意味着根的左子树和右子树是对称的，问题转化为比较两棵树的对称性。两棵树对称，首先要求两棵树的根的值相等，同时要求第一棵树的左子树和第二棵树的右子树是对称的，第一棵树的右子树和第二棵树的左子树是对称的。所以，可以使用递归解法，基本情况就是两棵树只有一个结点，且值相等，那么是对称的。

333. Largest BST Subtree

题意：给出一个二叉树（不一定是BST），求其中有最大结点数量的BST。follow up是要求O(n)时间。

解：此题可以分解为两个功能，一个是计算子结点总数，一个是判断是否是BST。常规解法就是，先后序遍历一遍计算出所有子节点数，耗时O（n），遍历期间内对每个结点为根的子树使用中序遍历判断是否是BST，消耗O(n)，总时间为O（n^2）。

如果要更快速，那么需要O(n)时间求出所有结点为根的子树是不是BST，使用以前的中序遍历是做不到的，因为那样需要从每个点出发计算。

O(n)的方法就是要利用递归思想，只需要O(1)时间判断一个结点为根的子树是不是BST，那就是后序遍历，判断方法就是左、右子树都必须是BST且左子树中的最大值要小于根节点的值且右子树中的最小值要大于根节点的值。既然都是后序遍历，那么可以将两个函数融合在一起进行一次遍历。每次返回四个值: 子树的最大值、最小值、是否是BST、以及子树的结点个数。可以新建一个类来作为返回类型。

106. Construct Binary Tree from Inorder and Postorder Traversal

题意：是给出中序和后序序列，来构建二叉树。

解：首先，分析出一点，就是每个元素都是unique的，不然给出的中序和后序序列不能唯一构建成一棵二叉树。

解题契机是后序序列的最后一个元素，最后一个元素必然是根，它把中序序列分为两个部分，左半部分是根的左子树所有元素，右半部分是根的右子树所有元素。所以，采用分治法，也就是把问题大化小，回归基本情况。以中序9，3，15，20，7，后序9，15，7，20，3为例。对后序序列从后向前扫描，3使得中序序列变为两个部分{9}和{15,20,7}，进一步，对于后序序列，我们知道3之前的三个元素（也就是{15, 7, 20}）必然是右子树部分，在往前的一个元素，或者说是开头的剩余部分{9}，就是左子树。也就是变成了两个子问题，也就是左右子树的构建，左子树是{9}对应{9}，右子树是{15,20,7}和{15, 7, 20}的对应。

对中序和后序都要使用start和end来标记下标，start > end的时候是基本情况返回，start == end也是基本情况返回。

PS.可以使用hashmap来快速得出中序数组中的元素到下标的映射。构建hash只需要扫描一次中序数组，以后就不需要每次都O（n）的去找了。

114. Flatten Binary Tree to Linked List

题意：将二叉树翻转为先序遍历的链表，只使用结点的右指针，空间复杂度要求为O（1）。

解：一开始想用分治法解决问题，但是发现左侧的问题解决后，我们无法知道它的最后一个元素，因此要快速排除掉这种思路。

另一种思路就是采取先序遍历，维持一个全局指针prev，指向当前构建链表的最后一个节点。

先序遍历思路遇到的一个问题就是，树的结构会被破坏，例如处理2作为1的下一个元素（右孩子）的时候，1的右孩子还没有被访问到，但是并没有关系，1先序遍历的时候，右孩子是谁其实以及知道了，可以在被破坏前备份下来，然后在先序遍历右子树时候继续使用。

遍历到的结点都是当前链表的最后一个结点，在加入prev的right，prev的left置为null，更新自己为prev。

也可以需要使用先遍历右子树的后序遍历（右左根）。后序遍历首先把root右子树（假设根为r）变成链表l，然后prev此时代表r的右子树的根。此时后序遍历下一个要访问的是root左子树中最右下的结点，该结点的right会指向l链表。也就是说，每个下一个后序遍历的结点的right指向前面遍历所有的结点组成的链表。这种方法和先序没有太大区别，只是递归结构初始值不会被破坏。

PS. 构建链表的期间不要忘了将访问结点左子树置空。

426. Convert Binary Search Tree to Sorted Doubly Linked List

题意：将BST按顺序（也就是中序）变成双向循环链表，并返回链表头，也就是BST里面的最小的值。

解：方法一：分治法。先将左右子树变为双向循环链表，然后与根进行拼接。基本情况需要处理，左右子树都不为空，一个为空，都为空的情况。

方法二：由于是BST，所以，双向循环链表的头尾，应该是容易得到的。首先，进行中序遍历，使用假头结点的方法，并使用全局的尾指针技巧（参考114题），就可以把BST转为双向链表，最后，使用假头节点和尾指针对双向链表进行收尾相连，形成双向循环链表。

285. Inorder Successor in BST

题意：BST给出root和一个结点p，求p的中序后继。

解：一种解法是：如果p有右孩子，那么找出p右孩子的最左下边的子结点就可以；

如果p没有右孩子：如果p作为父节点的左孩子的时候，那么p的后继是他的父节点；如果p作为父节点的右孩子，那么p的后继是沿着父节点向上走的路径（此路径是唯一的）上的第一个作为左孩子的结点的父节点。

具体解法就是从root开始找，如果cur的值比p的值小，说明cur应该变大，cur向右走；如果cur的值比p的值大，说明cur应该变小，cur向左走；如果cur的值等于p的值，那么cur置为空（走到右孩子），结束循环。每次向左走之前要记录下当前比p大的结点，向右走则不更新记录。这么做的原因就是记录下查找路径中当前结点中的作为左孩子的结点的父节点。这么说来，当p作为左孩子时候，其父节点也相当于查找路径上最后一个有左孩子的父节点。

方法二：直接从root开始找，如果当前值比p的值小，或者相等，那么向右走。如果右已经为空了，说明没有比p值大的，也就是没有后继，那么返回null。否则，已经知道答案肯定在当前结点的左子树中了，那么对左子树进行递归的查找，如果左边求出的结果确实比p值小，那么就是结果，否则还是左子树的根来作为结果。

方法三：直接从root开始找，如果当前值比p的值小，或者相等，那么向右走，否则向左走，并记录下当前的点，目的是记录下最后一个向左走的结点，也就是p的后继。相等时候向右走，然后比p大，然后向左走一直走到空结束。

173. Binary Search Tree Iterator

题意：为BST设计O（1）时间复杂度的中序next(), hasNext()的接口，空间复杂度要求为O（h）。

解：空间复杂度为O（h），所以也意味着不能使用hash表，只能使用其他数据结构，存储的信息是树高路径。使用stack来存储root沿左边走的路径，直到空停止，此时栈顶元素就是最小值了，如果栈顶元素被取出来，那么将沿它右孩子的左边路径访问并存储到栈上。栈不为空，说明hasNext。

PS.设计迭代器的题目都是使用迭代来解。

前序遍历和中序遍历使用栈的区别在于，一个是元素入栈的前一刻打印元素，一个是在出栈后一刻立即打印。

平摊后时间复杂度为O(1) ： https://stackoverflow.com/questions/12882424/in-order-traversal-complexity-in-a-binary-search-tree-using-iterators

116. Populating Next Right Pointers in Each Node

题意：完全二叉树，需要将每层的左结点指向右结点。空间复杂度要求为O（1）。

解：此题空间复杂度要求为O（1），所以不能使用queue来层序遍历，也不能使用递归，因为递归也存在调用栈。所以此题解法只能是沿着树进行遍历。

仍然按层序遍历。每一层把下一层的横向走法接通的思路，但是节省空间的方法就是，不在使用queue，而是根据上一层已经建立好的向右走的层序关系（上一步会把向右走的接通），遍历时候只需要使用指针对上层节点进行遍历就好。

完全二叉树意味着，每一层的起点就是沿着root向左走的节点。

117. Populating Next Right Pointers in Each Node II

题意：和116唯一不同之处在于不是完全二叉树，同样要求空间复杂度O（1）。

解：此题思路是，一层一层的访问，每一层访问的时候是上层是已经被建立好可以直接使用（root一层只有一个结点，看做建立好的），根据上一层构建当前层，然后当前层遍历的时候建立好下一层，然后切换到下一层继续遍历。

建立dummy结点，第一层是root，如果root的左孩子存在，则加到dummy链表最后面（使用链表尾插法，多一个last指针），如果右孩子存在，那么加入dummy最后面。root的next为空，说明结束root所在层的访问。然后，下一层的起点就是dummy的next了。然后同理的构建第3层的链表。记得每次都要把dummy后面的链表给剥离出来，即dummy.next = nullptr。

124. Binary Tree Maximum Path Sum

题意：求二叉树中最大路径和，路径允许经过root。

解：允许经过root的路径的意思是：一个点可以把自己和自己俩孩子连起来表示一条路径。

对每个结点的考虑，必须经过自己的且自己作为子树根的最大路径和。此时对他的孩子考虑，孩子自己考虑也是最大路径，所以有两种情况：（1）把自己当作链接左右桥梁来看：选两个孩子通过自己，如果两个孩子都为正，如果两个孩子只有一个为正，那选那个正的。

（2）考虑把自己链接到上一层。即使两个孩子为正，也只选择一个最大的孩子和自己做为当前结点的max。如果两个孩子都小于0，那么都不选。

此题解题的关键：要构建出一个”单孩子链”的概念，也就是当前结点所在子树问题传回上一层的时候，只上传自己或者自己的左或者右孩子，而不是把自己当作桥梁还传到上一层。

PS. 在递归过程中，上传到上一层的信息就是这种单孩子链的信息。

366. Find Leaves of Binary Tree

题意：给出二叉树的root结点，模拟叶子节点删除的顺序，每次作为一组，直到所有点被删光。

解：此题一开始准备使用左右子树结果按顺序合并，但是操作实在是麻烦。答案的做法是，计算每个结点自己子树的高度，如果高度相等的结点，那么就作为一层即可。做法就是，每次遇到新的高度，那么加一组，否则就在当前高度的那一组把该元素加上去。

156. Binary Tree Upside Down

题意：首先，树形状是有限制的：每个结点的右孩子必然存在和他同level的兄弟结点（也就是共享父结点的左孩子），要不就为空结点。翻转规则是对一个存在右兄弟的结点：他的父节点成为他的右孩子，他的右兄弟成为他的左孩子。

解：因为root的左孩子必有右兄弟，所以需要沿root左边走，对每个左孩子进行操作，发现是递归的，把左子树的子问题解决后，当前root的右孩子赋给左孩子的作为左孩子，root自身作为左孩子的右孩子，注意此时root已经是叶子了，所以左右孩子全部置为null，然后返回翻转左孩子后的新节点。递归的出口是：root为空，或者root左右节点都为空，返回root。

653. Two Sum IV - Input is a BST

题意：此题在BST中找2Sum。

解：此题解法并没有用到BST的中序有序的性质，反而是用了BST的元素不重复的性质，所以只需要遍历一遍BST，遍历过程中使用hash记录下已经访问的结点，然后看target - val是否在hash表中就可以了。

314. Binary Tree Vertical Order Traversal

题意：垂直的遍历二叉树。

解：此题一定要使用层序遍历，然后把值放入到对应的每一垂直层。现在问题是如何找垂直层。垂直层的找法是root是0，然后往左走一步减一，往右走一步加1。现在问题变为处理下标是负数的情况：两种方法：一种是先遍历一遍求出最左和最右值，然后每次减去最小值得出大于等于0的数；另一种方法更加简单，那就是使用没有正负数区别，而且和数组原理一样的map，先把结果存入map，然后把map还原成数组。此题map要使用treemap，因为要排序。

298. Binary Tree Longest Consecutive Sequence

题意：求二叉树中，最长相邻连续的序列，连续是指严格的1，2，3，…递增，相邻是指结点之间是连通的，且此题序列要求是严格从父节点到子节点的，不能由子节点经父节点在到兄弟节点。

解：此题使用dfs求解。dfs过程中，使用全局变量记录下最长的序列，然后，每层记录当前的最大值（这个值不能使用引用，要使用副本来保持往下传的是一致的），这个值在搜索过程中如果中断，需要重新置为1，表示从这个结点作为开头继续向下搜索。下一层的target就是上一层的root->val + 1，一旦下一层结点值等于target，那么当前层最大值就加1。这种树中考虑局部，全局解的问题应该使用dfs,或者使用后序遍历辅助函数。

549. Binary Tree Longest Consecutive Sequence II

题意：与298题相比，此题既可以是递增相邻序列，也可以是递减相邻序列，另外，可以连接左右子树。

解：此题处理局部最优解比较麻烦。比较简洁的思路就是递归。递归时候，返回两个值，一个是局部的递增最优，一个是局部的递增的，注意，这里的局部是指一定要考虑当前结点。然后，使用全局变量保存最大值。递归使用后序遍历，知道两个子节点的局部最优解之后，看自己能不能更新局部最优解，以及全局最优解。返回自己的局部最优解。

PS.1.全局最优解看原来全局最优解大，还是局部两个变量加起来减1（减1是因为两个局部都考虑了当前结点）哪个大。因为两个局部变量拼起来刚好是有序的。

2.每层处理要考虑左右孩子不为空，而且，左孩子处理后，右孩子在处理的时候，当前局部变量应该要和之前孩子处理之后的结果进行比较。

572. Subtree of Another Tree

题意：检查一棵树s是不是另一棵树t的子树。树中元素可以重复。

解：此题思路是分治。检查t树是不是和s树一样，如果一样，那么返回true，如果不一样，那么看t的左子树或者t的右子树哪一个和另一个树一样，有一个一样就返回true。检查两棵树是否一样，也是使用分治法。注意的是，比较完时候，如果一方结点不为空，那么也说明不是相同的树。

779. K-th Symbol in Grammar

题意：给出N表示扩展了N次，K表示第N次里面的第K位，求K位是0还是1，扩展的方式是从0开始，0变01，1变10。

解：此题非常有意思，只要将扩展的按二叉树来看，发现就是一颗满二叉树。所以这里利用一个规律，那就是如果K是偶数，那么说明他是父节点的右孩子，反之是左孩子，这样我们通过递归父节点是0还是1，就能反推自己是0还是1。来看一下K的分布。 1 1 2 1 2 3 4 1 2 3 4 5 6 7 8 … 求第N层的K的问题，K为奇数时候可以递归到父节点的 (K + 1) /2， K为偶数时候推到父节点的K/ 2。

652. Find Duplicate Subtrees

题意：求解二叉树中重复子树的根节点。

解：判断重复子树：就是将二叉树的每个点进行序列化，如果序列化出来的串是一致的，就说明重复。序列化具体操作方法就是指按照某种遍历顺序，结合额外信息组成的唯一的串。此题计算每个结点的序列化串，然后使用hash记录串出现次数，如果出现超过两次，那么就说明出现了重复子树。

776. Split BST

题意：实现BST的split操作，按节点值V将BST分为两颗子BST树(第一棵小于等于V，第二颗大于V)。

解：使用递归。如果V比root值小，那么说明root以及root的右子树可以作为一个部分，也就是可以作为分裂节点V的第二颗树T2的右子树存在，那么接下来就是对root的左子树进行考虑了，这是一个递归的过程，也就是说，root左子树将分裂成两棵树，然后其中的第二颗树（比V大的部分）作为上一步第二颗树T2的左子树存在，左树（比V小的部分）单独出来，作为上一步分裂节点的左子树。同理，在V比root值大的时候，那么也是相同的思路来处理。

再来看基本情况，那就是BST只有一个节点，那么将根据节点值比较的大小分为两个树，一个为空树，另一个为节点自己。 V等于root值的时候，根据题意，root属于第一颗树。

272. Closest Binary Search Tree Value II

题意：找出BST里面最接近x的k个数。

解：（1）暴力求解：inorder扫描，然后将数加入最大堆，最大堆的大小控制在小于k，里面元素存的是pair，pair第一个元素表示距离x的距离，第二个元素是结点大小，扫描一遍后得出答案，消耗时间O(nlogk)。

（2）可以使用BST中序是有序的性质，维持一个deque，然后在不足大小k的时候，直接加入deque尾，之后，如果在遇到值距离比deque的头距离x更近的，那么deque头弹出，然后在尾将该元素放入，这么做的原理就是，deque的头有两种情况，一种是他落在x的右边，此时当前扫描值一定也在x的右边，且不可能入选；另一种是他落在x的左边，此时扫描值可能在x左或者在x右，如果在x左，那么queue头后面的元素都只可能比头距离更靠近x，所以要弹的话就弹头；如果在x右，如果当前值比头更加靠近，作图发现，也是需要弹头，如果比头远，那么直接忽略。此方法时间复杂度O(n)。原理其实是滑动窗口，滑动窗口一开始包含所有的候选者，然后之后可以替换的就是窗口中最不符合条件的，这样最终窗口剩下的必然就是结果。

（3）使用额外O（n）空间，然后使用两头双指针，去除离x较远的n-k个元素，时间也是O(n)。

（4）使用两个中序迭代器，一个是最接近x且比x小的，另一个是最接近x的最大的，空间降到O(logn)，然后向两边扩展，扩展到k个数即可。此思路的原理就是logn的时间找到最接近x的两个元素，然后使用k的时间找出k个数，消耗时间为O(logn + k)。

437. Path Sum III

题意：给出一棵整数（有正有负）二叉树和一个整数target，现在求二叉树里面路径和等于target的路径有多少。路径不必经过root或叶子，只要是连续且向下的（不能有兄弟结点的这种）就可以。

解：先看一棵二叉树有多少条路径，如果路径要经过root和叶子，那么路径数和叶子树相同，因为叶子到root只有唯一一条路径。

现在是root到叶子上组合的选两个点就可以组成路径，假设n为叶子结点总数，如果二叉树是极度不平衡的，也就是一条线的时候，时间复杂度是O(n^2)，因为从n个里面选出两个就可以得到一个路径。

如果二叉树是平衡的，也就是高度为logn时候，root可以和任意其他结点组成一条路径，就是n-1条路径，而root的左孩子可以同样的方式组成n/2 - 1条路径，右孩子也一样，所以第二层是（n / 2 - 1）* 2 = n，每层都是n，且树高为logn，也就是说，时间复杂度是O(n logn)。此题如果使用暴力求解，那么时间复杂度是O(n^2)，最好情况下，时间复杂度也是nlogn。

暴力思路：从root遍历（先序遍历，或者说是深度遍历dfs），遍历到每个子结点，遍历过程中的路径长度记录下来作为候选结果看等不等于target。然后从root.left, root.right….出发遍历，也就是从剩余的子节点出发遍历。这种思路的时间复杂度是每次遍历的时间N，乘以遍历次数N，也就是O(N^2)。

优化思路：显然root遍历和root.left的遍历中间会有许多重复的结果，因此可以优化。反过来考虑，也就是自底向上的考虑，如果root的问题以及解决了，那么它对它的父节点有什么贡献，此时root的问题的解决意思是路径必须经过root。发现，如果知道有x条路径是基于root.left解的，那么实际上对root也没有什么贡献。在仔细考虑，发现root需要的root.left子问题的target不是sum，而是sum减去root值。也就是pathSum(root, sum) = pathSum(root.left, sum - root.val) + pathSum(root.right, sum - root.val)。因此，要解决pathSum(root, sum)，那么先解决pathSum(root.left, sum - root.val)和pathSum(root.right, sum - root.val)，依次类推，到达最后的基本情况，也就是叶子节点：此时root.left == null && root.right == null。那么看sum - parent.val是否为0，也就是看root的值等不等于它的target，如果相等，那么返回1，否则返回0。然而：到这这只是解决了pathSum(root, sum)的问题，也就是经过root的解，仍需要计算pathSum(root.left, sum), pathSum(root.right, sum)。。。

真正的优化思路：对于这种连续序列性质的和，都可以考虑前缀和技巧，也就是建立累加数组，然后连续点的和就变成两个端点相减的问题。这样root就是第一个元素，遍历到的元素都知道自己到达root的总和，这样所谓的累加数组其实就是累加和树了。然后对于找两个数相减等于target的问题，可以使用twoSum里面的技巧，也就是使用hash表记录下已知的前缀数，然后对于正在遍历的数，可以在O（1）的时间内知道：（1）有没有一个数可以和自己组合（加或减）来够成target，（2）如果hash表记录的信息还包括前缀数出现的数量，那么可以知道和之前一个数组成target的数量。

通过这种累加树的技巧，可以巧妙的避免中间节点需要单独来计算一套的这种尴尬问题。

方法一：暴力求解，对于树做一个先序遍历，先序遍历的时候，对root，进行root到其子节点遍历的dfs，过程中记录下来路径和等于target的数量。最终pathSum的结果看上去就是 pathSum(root) = dfs(root) + pathSum(root.left) + pathSum(root.right)。暴力求解的时间复杂度是O(N^2)。

方法二：使用前缀和+TwoSum的技巧。DFS的过程中，将到达当前结点的前缀和记录进hashmap，并记录其出现的次数(hashmap使用{前缀和 -> 前缀和数量})，在进入一个新节点后，先计算该节点的补数有多少个，就知道结束于该点有多少个路径和等于target，然后把当前前缀和数量加一，继续向下递归，注意在DFS退回上一层之后（回溯），（1）把当前前缀和的数量在hashmap中减一，（2）并注意恢复父节点的前缀和（例如左孩子访问完后恢复给父节点，以便父节点传给自己的右孩子）（注：有的dfs不需要恢复，传的是父节点的副本）。

时间复杂度是O(N)。

注意：hashmap一开始要加入哨兵值，也就是，preSum为0的数量默认是1。

求路径的数量和求具体路径完全不是一种思路，求具体路径，通过解空间分析知道时间复杂度，很难降低，而如果只需要知道数量，那就可以通过一些数学技巧来优化。