首先感谢CyC2018的详细笔记，这段时间受益匪浅，从一个更高的角度知道了数据结构与算法的关系——算法依赖于数据结构，就像是建筑材料与设计图纸的关系，特定的材料适合于实现某种独特的设计，一些材料可以实现许多设计方案，但是在价格、耐久度、美观方面各有优劣。
我们学习算法与数据结构的过程，不仅仅要认识数据结构的用途、算法的用途，更要在题海翻腾出感觉之后，去思考其之间的联系，去尝试着从问题的角度出发，考虑可行的算法中最为高效的那种，再考虑实现该算法的结构中空间复杂度最低的那一种。当你养成这种习惯去做题，乃至思考，你就会发现其中的乐趣的~
先从最基本的数据结构之一——树开始讲起吧~
定义
树（树状图），是一种数据结构，由n(n>=0)个有限节点组成的一个无环且有层次结构的集合。每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。
树的特性——递归
无论是二叉树还是多叉树，都会有一个很明显的特点——递归性，也就是说我们无论去看哪一个树的任意一个节点，自其往下仍旧组成一棵树。也就是说我们如果能够定义一种方法，将所有类型的树（空树、左右子树均为空、仅单边子树为空、左右子树都不为空）的情况都考虑进去，那这个方法就能递归地调用自身，通过若干次递归实现对这棵树的每一棵子树的进行相同的操作——统计、打印、查询、判定乃至改变其自身结构等等。
树的题型（用途）
1.递归（实现判定、统计、查询）
2.遍历（递归与非递归方式）
3.特殊树结构的用法
3.1.BST
3.2.Trie
1.递归
树的递归题型，更多的是让我们对其特有结构带来的递归特性有一个直观而全面的认识，培养自己的递归思维意识。一开始拿到树的递归题目，你可能会束手无策，这主要是你还没有养成“只看一棵树”。接下来我们从最近公共祖先这道题开始，学习这种思维模式。
LeetCode 面试题68-II
接下来的这张图，就是我们求解递归问题的一棵树模型——根节点root,左子树left,右子树right
“一棵树”
需要求解p、q的最近公共祖先，我们就尝试从pq节点存在于这棵树的位置的不同来进行分类讨论
1.永远先考虑root是否为null，即使题目要求里面说了树不为空，你的递归仍然有可能不可避免的要到达叶子节点的左右子树，一旦你的递归终止条件需要靠判定节点是否为空来完成的话，就一定要考虑root为null的情况。显然，这里当 时，显然这三部分都没有我们要的最近公共祖先，我们对这样的root返回null。
我们需要求解的是pq的公共祖先，就这个目标来讲，pq的优先级是相同的，所以我们在分析的时候尝试用：一个目标节点，另一个目标节点来思考，避免陷入无意义的对称分析之中。
2.对于非空节点root，只有两种情况——是一个目标节点（p或q），不是目标节点
2.1.如果它是某一个目标节点，那么另一个目标节点一定在左子树或者右子树上。这里说明一下，因为我们是从根节点开始逐层向下递归，所以遇到的第一个p或者q，剩下的节点只可能在root下面，此时root就是我们需要求解的最近公共祖先
2.2.如果它不是目标节点，那么pq就存在三种可能——a)左右子树上各一个 b)左子树或者右子树上独占两个 c)左右子树上都没有目标节点，此时我们递归地去求解左子树、右子树，将返回结果保存下来，如果一棵子树上没有pq，那么一定会返回null，反之返回值为p或者q
对于情况a)，显然root就是我们要求解的结果；
对于情况b), 以上递归的返回结果一定有一个为空，另一个返回的就是含有p、q的子树的递归结果；
对于情况c), 很显然这一整棵树都不是我们要求解的树，直接返回null就行
补充：虽然题目没有明确说明pq是否可以为空，本着全面思考的方针，在进行一个补充讨论——pq只要有任意一个为空，最有求解的结果一定是空
代码：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == null || q == null)return null;
if(root == p || root == q)return root;
TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
TreeNode rightResult = lowestCommonAncestor(root.right, p ,q);
if(leftResult != null && rightResult != null)return root;
else{
if(leftResult == null)return rightResult;
if(rightResult == null)return leftResult;
}
return null;
}
总结：先分析根节点root的所有情况，能在root处进行返回的要提前返回，不能的再交由左右子树的递归去解决，只分析这三个部分，递归的分析就用简写的函数表达式代替就行（默认你已经实现了递归，直接调用）。
结尾再分享一个关于该题的视频，本文的分析思路也源于此，所谓吃透题目，就是掌握树的递归特性和“一棵树”模型的思维模式。
网友评论