第一章 链表 第二章 二叉树 第三章 栈、堆和队列 第四章 哈希表 第五章 字符串 第六章 数组和矩阵（不是重点） 第七章 图 第八章 位运算 算法——1 双指针 算法——2 排序 算法——3 贪心思想 算法——4 分治（含二分） 算法——5 搜索（含深搜宽搜） 算法——6 动态规划 算法——7 数学 算法——8 并查集
二叉树的部分是面试中的超级重点，几乎是必问的。
对二叉树的掌握主要是前序、中序、后序遍历思想的灵活掌握，最重要的是灵活的使用深度优先搜索思想和广度优先搜索思想，这部分由一点点需要思考，但是不要有害怕的这种想法，因为掌握的套路之后，再加上有题目的经验，我们总能够想到方法的。
下面依然是对二叉树的题目进行了分类整理。题目来源是leetcode100题和剑指offer，记住，质比量重要，谨慎对待每一题，透彻理解里面的思路和思想。
自己写的时候，不要看别人的代码，整理好思路后，自己在IDE里写代码，然后在比较不同。 一共24题，其实并不多，哈哈，加油，加油……
中序遍历：左子树->跟->右子树 第一种方法就是递归，这种方法无需多言，数据结构都学过；
第二种方法就是用栈，大家都知道递归是可以用栈模拟的，这里学会用栈的方法，有助于我们了解到中序遍历的过程。 用到的数据结构——Deque双端队列 既可以操作队列头，也可以操作队列尾，我们可以用这个数据结构实现栈、队列，非常非常好用哦……
我一般解题的时候都用不抛出异常的方法，这一题是要作为栈使用，就用入栈：offerLast(e)、出栈：pollLast()、栈顶：peekLast();当然你要用first结尾的也一样可以。
思路---------------------- （1）根据中序遍历的定义，需要先递归左节点，再递归左节点的左节点，这样一直让左节点入栈
while(root!=null){ stack.offerLast(root); root = root.left; }（2）每当上面代码退出的时候，也就是递归左节点到了尽头，接着就可以从当栈中弹出一个元素，加入结果序列后，让该节点的right 入栈。 当然前提值栈不空 stack.peekLast() != null
root = stack.pollLast(); res.add(root.value); root = root.right;//到右子树去递归入栈去(3) 接着回到（1）循环，直到栈空为止。总之，我们要尽可能的向left走，万般无奈向右边走一步，在弹栈的时候添加到结果集。
中序遍历代码-------------------------------------------------------------------------
class solution{ /** *递归法----- */ void inorder(TreeNode root,List<Integer> res){ if(root==null) return; inorder(root.left,res); res.add(root.value); inorder(root.right,res); } /** *栈模拟 */ public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); while(stack.peekLast()!=null || root!=null){ while(root!=null){//一路向左 stack.offerLast(root); root = root.left; } root = stack.pollLast();//输出结果 res.add(root.val); root = root.right;//拐弯到右子树 } return res; } //补充——前序遍历的栈模拟法 public List<Integer> preorderTraversal(TreeNode root){ List<Integer> res = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); while(stack.peekLast()!=null || root!=null){ while(root!=null){//一路向左 res.add(root.val);//递归的时候就输出结果 stack.offerLast(root); root = root.left; } root = stack.pollLast();//拐弯到右子树 root = root.right; } return res; } //补充——后序遍历的栈模拟法——右左跟 输出再倒序 public List<Integer> preorderTraversal(TreeNode root){ List<Integer> res = new ArrayList<Integer>(); Deque<TreeNode> stack = new LinkedList<TreeNode>(); while(stack.peekLast()!=null || root!=null){ while(root!=null){//一路向右 res.add(root.val);//递归的时候就输出结果 stack.offerLast(root); root = root.right; } root = stack.pollLast();//拐弯到左子树 root = root.left; } return Collections.reverse(res); } }思路：递归分治构造二叉树，其中找中序中跟的位置是用的map优化 时间复杂度：O（n），n是节点的个数 空间复杂度栈深度h<map长度n，所以O(n)
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer,Integer> map = new HashMap<>(); for(int i=0;i<inorder.length;i++) map.put(inorder[i],i); return recur(preorder,0,preorder.length-1,inorder,0,inorder.length-1,map); } public TreeNode recur(int[] preorder,int preleft,int preright,int[] inorder,int inleft,int inright,Map<Integer,Integer> map){ if(preleft>preright || inleft>inright) return null; TreeNode root = new TreeNode(preorder[preleft]); int pIndex = map.get(preorder[preleft]); root.left = recur(preorder,preleft+1,pIndex-inleft+preleft,inorder,inleft,pIndex-1,map); root.right = recur(preorder,pIndex-inleft+preleft+1,preright,inorder,pIndex+1,inright,map); return root; } }要求将每个节点的值更新为比她大的节点值之和 采用右子树-根节点-左子树的遍历方式，设置一个全局变量，每次记录过程中累加的值。我们可以想象一下前序遍历的结果是一个递增序列，所以这种递归的结果就是一个递减的序列，每次让前面的累加，就得到结果了。 我们之后有一题——判断二叉搜索树，其实那一题可以用类似的做法，就是前序遍历，每次判断是不是比前一个数大。
/** *首先是用栈模拟，非递归法 */ class Solution { int sum = 0; public TreeNode convertBST(TreeNode node) { TreeNode root = node; if(root == null) return null; LinkedList<TreeNode> stack = new LinkedList(); while(!stack.isEmpty() || root!=null){ while(root!=null){ stack.push(root); root = root.right; } TreeNode cur = stack.pop(); sum+=cur.val; cur.val = sum; root = cur.left; } return node; } } /** *下面是递归的方式 */ class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if(root==null) return null; convertBST(root.right); sum+=root.val; root.val = sum; convertBST(root.left); return root; } }太简单了，但是要学会将k设置为全局变量，否则，作为参数是不可以每次右-中-左，在中-1，应该设一个全局变量。
class Solution { int a = 0,k; public int kthLargest(TreeNode root, int k) { this.k = k; help(root); return a; } private void help(TreeNode root){ if(root==null) return ; help(root.right); k--; if(k==0){ a = root.val; return; } help(root.left); } }法一 DFS递归 最大深度 = 1+max{左子树最大深度，右子树最大深度} 时间复杂度是O(n) 空间复杂度是O（height）这是栈的深度 也可以看做是后序遍历，先计算左右子树的深度，再算根节点的深度，返回的是根节点的深度
class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; return 1 + Math.max(maxDepth(root.left) , maxDepth(root.right)); } }法二 BFS层序遍历一遍，每次处理完一层 ，level加一，最后level数量就是最大深度. 时间度复杂度O（n），空间复杂度O（n），队列存储元素个数。
class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; int level = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ int size = queue.size(); for(int i = 0;i<size;i++){ TreeNode node = queue.poll(); if(node.left!=null) queue.offer(node.left); if(node.right!=null) queue.offer(node.right); } level++; } return level; } }其实就是遍历一遍，所以宽搜深搜都可以。 深搜，当有一个是空的时候，合并结果是非空的那颗树，否则两棵树都不空，则合并的结果为：当前节点改value，然后递归合并左子树右子树。 时间复杂度：0（min（t1个数，t2个数）） 空间复杂度是：O（min（t1深度，t2深度））
class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if(t1==null) return t2; if(t2==null) return t1; t2.val = t1.val + t2.val; t2.left = mergeTrees(t1.left,t2.left); t2.right = mergeTrees(t1.right,t2.right); return t2; } }当然，我们也可以想象成自己是在用先序遍历，先处理根节点，然后处理左子树、右子树。
法一：后序遍历法 就是让左右子树先交换，也就是一直押栈，最后左右子树都翻转成功了，再处理根节点。交换root.left和root.right
TreeNode invertTree(root){ if (root == null) // 遍历到null节点时，不用翻转，直接返回它本身 return root; invertTree(root.left); // 递归压栈压到底 invertTree(root.right); TreeNode temp = root.left; // 执行交换 root.left = root.right; root.right = temp; return root; }思路二：先序遍历法 就是根节点先交换左右子树，然后再处理左右子树
TreeNode invertTree(root){ if (root == null) { // 遍历到null节点时，不用翻转，直接返回它本身 return root; } TreeNode temp = root.left; root.left = root.right; root.right = temp; invertTree(root.left); invertTree(root.right); return root; }解法一： 两棵树镜面对称 = 根相等 && 1树的左子树和2树右子树镜面对称 && 1树右子树和2树左子树镜面对称。 时间复杂度O（n） 空间复杂度O（深度）
class Solution { public boolean isSymmetric(TreeNode root) { return ismirror(root,root); } public boolean ismirror(TreeNode t1,TreeNode t2){ if(t1==null&&t2==null) return true; if(t1==null || t2==null) return false; return t1.val==t2.val && ismirror(t1.left,t2.right) && ismirror(t1.right,t2.left); } }解法二： 开始连续让两棵树的根节点如队列， 然后每次从队列里poll出两个元素，看看是不是相等 再分别让1元素的左和2元素的右进去，1元素的右和2元素的左进去，当然再两者是镜面的情况下。 时间复杂度O（n） 空间复杂度O（n），节点进队出队，不会超过n
class Solution { public boolean isSymmetric(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); queue.offer(root); while(!queue.isEmpty()){ TreeNode t1 = queue.poll(); TreeNode t2 = queue.poll(); if(t1==null&&t2==null) continue; if(t1==null||t2==null) return false; if(t1.val!=t2.val) return false; queue.offer(t1.left); queue.offer(t2.right); queue.offer(t1.right); queue.offer(t2.left); } return true; } }当前树根节点叫做root，求p和q的最近公共祖先，使用后序遍历的顺序，从最左叶子和它的兄弟开始找p和q，一点一点向他们的爸爸爷爷上蔓延。发现p或者q了，返回，表示找到了。
root = p,返回p——递归终止root = q，返回q——递归终止root不是p也不是q，递归找p、q分别在root的left子树和right子树，此时最近祖先就是root，返回——递归终止 class Solution{ public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){ if(root==null || root==p || root==q)//从根节点到叶子的找到的是第一个q或者p的那个节点 return root; //去左右子树中找p、q的最近祖先 TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left==null) return right;//左子树没有p也没有q if(right==null) return left;//右子树没有p也没有q return root; } }解法一：根据递归定义，二叉搜索树的左子树都小于根节点，右子树都大于根节点。每个节点都有一个上下界。
class Solution{ public boolean isValidBST(TreeNode node){ return withinBounds(node,Long.MIN_VALUE,Long.MAX_VALUE); } public boolean withinBounds(TreeNode root,long low,long high){ if(root==null) return true; if(root.val<=low || root.val>=high) return false; //左右子树的上下界是否满足条件，小心左子树更新上界为当前节点，右子树更新下界为当前节点。 return withinBounds(root.left,low,root.val) && withinBounds(root.right,root.val,high); } }解法二：二叉搜索树的中序遍历应该是一个递增的序列。 二叉搜索树的的中序遍历的结果应该是一个递增的序列。所以我们可以后序遍历一个二叉搜索树，设置一个全局变量存储上次的那个值。
class Solution { Long lastVal = Long.MIN_VALUE;//设成Long的最小值，防止节点的值=Integer.MIN_VALUE public boolean isValidBST(TreeNode root) { if(root==null) return true; if(!isValidBST(root.left)) return false;//左子树 if(root.val<=lastVal) return false;//当前根节点 lastVal = (long)root.val; return isValidBST(root.right);//右子树 } }方法一： 后序遍历，先让右子树展开，再展开左子树，然后展开跟
class Solution { public void flatten(TreeNode root) { if(root==null) return; flatten(root.right); flatten(root.left); TreeNode cur = root.left; if(cur!=null){ while(cur.right!=null) cur = cur.right; cur.right = root.right; root.right = root.left; root.left=null; } } }方法二：迭代，从根节点开始，每次展开当前最右边的那个节点的左子树
这一题简单的很，回溯递归，每次判断跟节点到当前叶子节点的和是不是等于sum
class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root==null) return false; if(root.left==null && root.right==null){ if(sum==root.val) return true; else return false; } sum-=root.val; if(hasPathSum(root.left,sum)==true) return true; if(hasPathSum(root.right,sum)) return true; return false; } }和112没啥区别，只要每次发现到达叶子节点且满足条件的时候，就将记录当前路径放入结果集。
class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> paths = new ArrayList<>(); if(root==null) return paths; dfs(root,sum,paths,new ArrayList<>()); return paths; } private void dfs(TreeNode root,int sum,List<List<Integer>> paths,List<Integer> curPath){ if(root==null) return; sum-=root.val; if(sum==0 && root.left==null && root.right==null){ curPath.add(root.val); paths.add(new ArrayList(curPath)); curPath.remove(curPath.size()-1); } curPath.add(root.val); dfs(root.left,sum,paths,curPath); dfs(root.right,sum,paths,curPath); curPath.remove(curPath.size()-1); } }发现短路径中的最大者一定是叶子节点之间，所以问题就转化成了——求叶子节点间最短路径中的最大值 这一题不是直接求的，必须转化为求根节点到孩子节点的深度那一题，中序遍历，先求左深度，再求右深度，这时候就可以更新最大距离了。 叶子节点间最短路径 = 公共父节点到两个叶子的高度之和。如左子树的深度是5，有4条边，右子树深度是4，有3条边，那么它们间的直径就是9，还有到叶子节点的那两条边。
求深度可以用深搜的求节点深度的方法：深度 = max{左子树深度，右子树深度} + 1。这种方法求出的最大深度不是指边的深度，而是层数，比如说如果只有一个节点，这个节点的深度就是1，而不是0。
设置一个全局变量max存储最大 最短路径 max = max{left深度 +right深度，max}
class Solution { int maxlen = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxlen; } public int depth(TreeNode root){ if(root==null) return 0; int left = depth(root.left); int right = depth(root.right); maxlen = Math.max(left+right,maxlen); return Math.max(left,right) + 1; } }这一题和上面一题 求最大直径类似，也是不能直接求，怎么办呢？ 求以当前根节点到为起点的一条路径,使得该路径的节点值之和最大。这也是一个后序遍历过程，左子树为首的最大、右子树为首的最大、当前节点。更新max=MAX{max，root，root+left，root+right，root+left+right} 简化的思路——help（root）返回值是以root为出发点的最大贡献值，要不是0，要不是正数。因为如果子树的贡献为负数，就不要子树就好，这样也好写代码。
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { help(root); return maxSum; } private int help(TreeNode root){//计算root为根这条树的最大贡献 if(root==null) return 0; int left = Math.max(help(root.left),0);//计算左子树的最大 int right = Math.max(help(root.right),0);//右子树最大贡献值 //更新maxSum包含当前节点时的最大值 maxSum = Math.max(maxSum , root.val+left+right); return root.val + Math.max(left,right);//该子树的最大贡献值 } }这一题和i前两题一样也是后序思路，用一个全局变量记录最长的长度，help（root）计算以root出发最长单向的同值路径长度(层数)，我们的最长变量就在算完左右的时候更新。
class Solution{ int maxlen = 0; public int longestUnivaluePath(TreeNode root){ help(root); return maxlen; } private int help(TreeNode root){ if(root==null) return 0; int left = help(root.left); int right = help(root.right); if(root.left!=null && root.left.val==root.val) left++; if(root.right!=null && root.right.val==root.val) right++; maxlen = Math.max(maxlen,left+right); return Math.max(left,right); } }这一题就是使用的动态规划的思想，每次看看不放根节点和放根节点的时候，各自的最优值是多少财宝使用后序遍历的思想，因为当前节点的最优值需要起来孩子的结果。
class Solution { public int rob(TreeNode root) { if(root==null) return 0; int[] a = dp(root); return Math.max(a[0],a[1]); } private int[] dp(TreeNode root){ if(root==null) return new int[]{0,0};//0代表不选，1是选 int[] left = dp(root.left); int[] right = dp(root.right); int[] good = new int[2]; good[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]); //选root good[1] = left[0]+right[0]+root.val;//不选root return good; } }计算1-n可以组成的BST个数，发现可以使用动态规划
class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; dp[0] = 1; for(int i=1;i<=n;i++){//以0-i可以构成的个数 for(int j=1;j<=i;j++){//0-i分别作为根节点 dp[i]+=dp[j-1]*dp[i-j]; } } return dp[n]; } }我们已经知道这一题是存在大问题、小问题的情形的，所以总体上就用分治的思路，比如要计算【l，r】的所有二叉树，就把它分解为当l-r分别是根节点的时候，分别计算l——i-1和i+1——r的二叉树集合，两个集合排列组合作为当前跟的左右子树。就完成了本体的解答。
class Solution { public List<TreeNode> generateTrees(int n) { if(n==0) return new ArrayList<>(); return dfs(1,n); } private List<TreeNode> dfs(int l,int r){//从l到r可以构成的二叉搜索树 List<TreeNode> res = new ArrayList<>(); if(l>r){ res.add(null); return res; } for(int i=l;i<=r;i++){ List<TreeNode> left = dfs( l,i-1); List<TreeNode> right = dfs(i+1,r); for(TreeNode leftNode:left) for(TreeNode rightNode:right){ TreeNode root = new TreeNode(i,leftNode,rightNode); res.add(root); } } return res; } }这一题挺简单的，我们知道什么是前缀树，构件它就行了。根据题意可以是个最多26叉的数。
方法一： 定义一个前序和数组，存放前序和。从i-j暴力枚举pre[j]-pre[i-1],O(n^2)复杂度
方法二： 定义一个当前前序和变量和一个哈希表，存放数组的前序和 以及该前序和出现的次数 一次遍历，每次先更新检查 当前前序和-sum 在hash中出现的次数，累加之，然后到更新这个hash，再次到下一个节点。
方法一： 从前两题的路径总和我们可以发现，我们的一般的解法只能计算出从根节点出发到下面的路径，是不是和==sum，如果题目是这样的，我们会发现简单很多，直接先序遍历一遍（深搜回溯），每次看看当前节点的当前路径和是不是sum就可以了，也就是我们的helper函数。 然而，题目不是让我们必须从跟姐点出发，所以要遍历一点这棵树，每次把当前节点作为跟节点，也就是出发点。 结果 = 根节点作为出发点个数 + 左子树做出发点 + 右子树做出发点
时间复杂度：O（N*N） 空间复杂度：O（N）
class Solution { public int pathSum(TreeNode root, int sum) { if(root==null) return 0; return helper(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum); } //从root出发遍历 //每次查看是否 [跟，当前节点]==sum //上一步个数 + 跟——左子树 + 跟——右子树 private int helper(TreeNode root,int sum){ if(root==null) return 0; //当前节点是结束点时个数 sum -= root.val; int res = 0; if(sum==0) res++; res+=helper(root.left,sum);//向左走接着下来多少个 res+=helper(root.right,sum);//右作为结束点 return res; } }方法二 前缀和的方式优化,用一个map保存从根节点到当前节点的各个前缀和，当然，因为回溯，这个map存的就是当前的单支路径上的前缀和。以及出现那些前缀和的个数。比如数组[1,2,3,0],前缀和map就是{0:1, 1:1, 3:1, 6:2} 我们一次遍历这棵树，如果 当前节点的前缀和-sum==target，且在map中target的出现的个数是3，就说明了以当前节点作为接结束，父辈节点作为开始的满足条件的路径有3条，累加到结果了即可。
时间复杂度：O（N） 空间复杂度：O（h）
class Solution { public int pathSum(TreeNode root, int sum) { if(root==null) return 0; HashMap<Integer,Integer> map = new HashMap<>(); map.put(0,1); return helper(root,sum,map,0); } //从root出发遍历，相当于先序遍历，每次查看是否当前节点到跟的路径==sum，是则+1 private int helper(TreeNode root,int sum,HashMap<Integer,Integer> map,int curSum){ if(root==null) return 0; int res = 0;//保存结果路径条数 curSum+=root.val;//更新当前前缀和 if(map.containsKey(curSum-sum))//当前节点可以和父亲们构成满足条件的路径 res+=map.get(curSum-sum); //当前节点放入前缀和map，为递归左右子树做准备 map.put(curSum,map.getOrDefault(curSum,0)+1); res+=helper(root.left,sum,map,curSum); res+=helper(root.right,sum,map,curSum); //不用remove了，没有就减一就好，分数==0不会影响 map.put(curSum,map.getOrDefault(curSum,1)-1); return res; } }