本文共 2542 字，大约阅读时间需要 8 分钟。
1.题目思路
1. 100.Same Tree
关键词：值、结构 思路： （1）采用递归。递归时先要搞清楚结束条件，本例有三个结束条件 ①两者都为NULL（值、结构相同） ②一者为NULL，一者不为NULL（结构不同） ③结构相同，val不同（值不同） （2）采用迭代 这种可以使用递归的结构，要保证用迭代也能完全遍历地话，需要使用stack 其他没什么特别的。2. 101.Symmetric Tree
关键词：值、结构 思路：这一题与100大同小异，只需要把递归的时候，调用参数对调即可。 3. 102.Binary Tree Level Order Traversal 关键词：level 思路： （1）采用递归，找到结束条件：root==NULL 除了结束条件，其他情况都是一致的处理。 引入了一个level来表征是第几层，每向下一层，level+1。 并且level还要用来判断，vector<vector<int>>有没有某层得记录。 方法是比较level和vector<vector<int>> result.size() 4. 104.Maximum Depth of Binary Tree 关键词：cur、max 思路：depth of a tree表示，根节点到某叶子节点的距离 递归关键还是找清楚结束条件:!root 其实!root并不表示父亲节点为叶子节点，但是由于这里求的是最长距离， 所以再增加一个cur>max，对max进行条件判断即可。 5. 107.Binary Tree Level Order Traversal II 关键词：level 思路：与102完全一样，最后对结果进行一次reverse即可。6. 110.Balanced Binary Tree
关键词：不平衡 思路：还是利用递归，重点是理清楚递归结束条件 平衡结束条件:!root 不平衡结束条件：①左子树不平衡②右子树不平衡 ③自身不平衡（左右子树高度差超过1） 7. 111.Minimum Depth of Binary Tree 关键词：cur、min、hasBrother 思路：类似于求最长depth，但是这里有个巨大的陷阱。 !root并不表示父亲是叶子节点，这个时候，我们可以再加入一个判断条件， 就是hasBrother，如果没有brother，并且!root，那么父亲一定是叶子节点。 归根结底是要弄清楚，这个depth of a tree的概念 8. 112.Path Sum 关键词：cur、sum 思路：结束条件1：!root 结束条件2：!(root->left) && !(root->right) 注意，这里将!root也作为一个结束条件，简化了递归时的条件判断， 这样节点将所有情况枝分解为3种情况，编码简单清爽很多。 9. 226. Invert Binary Tree 关键词：swap 思路：这个类似于，112 而且这里分成两种情况即可 情况1：!root || (!(root->left) && !(root->right)) 情况2：else 10. 235.Lowest Common Ancestor of a Binary Search Tree 思路：这一题的解法非常多分为两大类 I。利用BST性质的 （1）由于最近的公共父节点肯定满足，p->val < root->val < q->val的 从root开始找起，最近公共父节点肯定是第一个满足这个性质的。 之前的节点，要么大于两个目标节点，要么小于两个目标节点。 如果大于，下一步走左 如果小于，下一步走右 （2）可以分别找到两个节点的路径信息，放在vector里面，然后进行比较。 这个找路径信息也有讲究，也可以利用BST的信息， 本身BST就是用来干这个的。 II。不利用BST性质，就当做BT的 （1）可以分别找到两个节点的路径信息，放在vector里面，然后进行比较。 不利用BST的话，就只有进行朴素搜索了，遇到了就返回。 这里当然还有个优化是将中间路径用引用表示的。 （2）我这边还有个笨办法。 分别朴素深搜，找到两个目标节点的层数。在找的过程中记录之前层出现过的所有节点信息。 把同一层的放在一个vector里面。 然后比较两个目标节点的层数，然后从较小的那个层数开始对这个层所有的节点遍历， 看能不能搜索到两个目标节点。如果不可以的话，就遍历上一层。 11. 257.Binary Tree Paths 思路：直接朴素深搜，然后打印即可。 有将int转换为字符串的过程，还有判断->符号。 还是分3种情况就好。 ①!root ②!(root->left) && !(root->right) ③else 2.题型总结 1.递归判断 输入两棵树的情况三种情况区分
①两者同时为假 ②一者为假，一者为真 ③两者都为真 if(!p && !q){ }else if(!p || !q){ }else{ } 本来，(!p || !q)也包含，两者同时为假的情况， 但是这里是else if所以，只剩下一者为假一者为真。 这里在不关心具体哪个为真，哪个为假的情况下，十分好用。 2.递归判断输入一棵树的情况
将树的递归写成3种情况
（1）没有指针 （2）左右都为假 （3）其余情况 if(!root){ }else if(!(root->left) && !(root->right)){ }else{ } 3.搜寻特定节点路径的时候，中间变量用引用 本来这个中间变量用局部变量，然后进行值传递，最后找到了再传递最终结果。 但是为了提高效率，减少中间变量拷贝的不必要的消耗，可以将它使用为引用。 但是，因为这是引用，所以对于那些无效搜索，必须要进行相应地处理， 所以其处理方式，就是将所有的提前return的 要么就是设置好最终结果了 要么就是不要对这个中间结果进行修改 如果是修改了中间结果的没有搜索到的正常对出，加上一个pop_back就可以抵消修改。 3.思考 1.指针直接可以作为if里面的判断条件 当指针存在时转换为真 当指针为NULL时转换为假转载地址：http://ciiei.baihongyu.com/