前言
前段时间，写了面试必备的一系列文章，反应还不错。有一些读者反馈说，能不能整理一些面试常见的算法。前段时间，我恰好总结了 LeetCode 常见的面试算法题目。
Android 面试必备 - http 与 https 协议
Android 面试必备 - 计算机网络基本知识（TCP，UDP，Http，https）
Android 面试必备 - 系统、App、Activity 启动过程
面试官问， https 真的安全吗，可以抓包吗，如何防止抓包吗
慢慢得，我发现算法也是一个可以通过练习慢慢成长的。
- 首先我们要掌握基本的数据结构，数组，链表，哈希表， Set，二叉树，堆，栈等。你要知道他们有什么优缺点，适应场景是什么，时间复杂度和空间复杂度是多少。而不能知道简单的 API。
- 接着，掌握了这些基本的数据结构之后，一些基本的算法你也要掌握以下，比如快速排序，归并排序，对排序，二分查找。这些基本的一定要掌握，面试当中经常也会问到。
- 分类刷题，我们在力扣上面可以看到，https://leetcode-cn.com/problemset/algorithms/ ，刷题是可以按标签来的。比如链表，数组，二分查找，二叉树，动态规划等
- 学好算法不是一日之功，需要长期的积累。建议的做法是每天做一两道题，题目不在多，贵在于理解。坚持一两个月，你会发现你的感觉逐渐好起来了
废话不多说了，开始进入今天的正文，LeetCode链表知识点&题型总结
二叉树的概念
二叉树（Binary Tree）是包含n个节点的有限集合，该集合或者为空集（此时，二叉树称为空树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
一棵典型的二叉树如下图所示：
由上述的定义可以看出，二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。
二叉树种类
满二叉树
对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。
完全二叉树
对于一棵具有n个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。
二叉排序树：
又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 没有键值相等的节点
二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找）
平衡二叉树：
又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。
红黑树：
红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。
哈夫曼树：
给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。
遍历方式
二叉树主要有四种遍历方式
- 先序(先根)遍历：即先访问根节点，再访问左孩子和右孩子
- 中序遍历：先访问做孩子，再访问根节点和右孩子
- 后序遍历：先访问左孩子，再访问右孩子，再访问根节点
- 层次遍历：按照所在层数，从下往上遍历
前提：这里先给出测试中的二叉树结构，如下图所示
该二叉树对应的几种遍历方式的结果顺序：
- 先序遍历：10->6->4->8->14->12->16
- 中序遍历：4->6->8->10->12->14->16
- 后序遍历：4->8->6->12->16->14->10
- 层次遍历：10->6->14->4->8->12->16
递归
一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理。
1. 树的高度
1.0 求二叉树的最大层数(最大深度)
104. Maximum Depth of Binary Tree (Easy)
这道题目的解法其实很简单
- 如果二叉树为空，二叉树的深度为0
- 如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
public int maxDepth(TreeNode root) { if (root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }
1.1 二叉树的最小深度
LeetCode：Minimum Depth of Binary Tree
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; int left = minDepth(root.left); int right = minDepth(root.right); return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1; } }
2. 平衡树
110. Balanced Binary Tree (Easy)
3 / \ 9 20 / \ 15 7
思路
平衡树左右子树高度差都小于等于 1
private boolean result = true; public boolean isBalanced(TreeNode root) { maxDepth(root); return result; } public int maxDepth(TreeNode root) { if (root == null) return 0; int l = maxDepth(root.left); int r = maxDepth(root.right); if (Math.abs(l - r) > 1) result = false; return 1 + Math.max(l, r); }
3. 两节点的最长路径
543. Diameter of Binary Tree (Easy)
Input: 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
private int max = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return max; } private int depth(TreeNode root) { if (root == null) return 0; int leftDepth = depth(root.left); int rightDepth = depth(root.right); max = Math.max(max, leftDepth + rightDepth); return Math.max(leftDepth, rightDepth) + 1; }
4. 翻转树
226. Invert Binary Tree (Easy)
public TreeNode invertTree(TreeNode root) { if (root == null) return null; TreeNode left = root.left; // 后面的操作会改变 left 指针，因此先保存下来 root.left = invertTree(root.right); root.right = invertTree(left); return root; }
5. 归并两棵树
617. Merge Two Binary Trees (Easy)
Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: 3 / \ 4 5 / \ \ 5 4 7
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null && t2 == null) return null; if (t1 == null) return t2; if (t2 == null) return t1; TreeNode root = new TreeNode(t1.val + t2.val); root.left = mergeTrees(t1.left, t2.left); root.right = mergeTrees(t1.right, t2.right); return root; }
6. 判断路径和是否等于一个数
Leetcdoe : 112. Path Sum (Easy)
Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
路径和定义为从 root 到 leaf 的所有节点的和。
public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.left == null && root.right == null && root.val == sum) return true; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }
