此处主要是记录一些自己觉得精彩的LeetCode题解和心得。
1. Tree
预备. AVL 树
AVL树是一种平衡二叉树，其平衡因子（某个节点的左子树的高度减去右子树的高度得到的差值）的绝对值都不超过1。在每次添加或者删除的情况下，其都会进行检验，如果不满足这个条件，就进行相应的左旋和右旋，从而使其满足平衡因子的差值的绝对值不超过1的要求。
那么为什么在许多数据结构之中使用红黑树而不是AVL树呢？
红黑树相比AVL树而言，其更不平衡，这也就意味着其查找时候所需要的时间更多，但是其插入，删除等的所需的再平衡时间更短。我们使用数据结构，大部分情况是要对数据进行改动的，那么这种情况下不使用AVL树而使用红黑树就很显而易见了。
一些解题心得：
- 对于树而言，其递归式的解法必定是从上向下的，而且可以操作的也无非就是TreeNode本身， TreeNode.left, TreeNode.right这三个。那么对于一些”从根节点到叶子节点“是否满足某种条件的问题（https://leetcode.com/problems/path-sum/description/），就要拆分成”每一层除了根节点之外是否满足剩下的条件“。
- 如果有对于两棵树的检查(https://leetcode.com/problems/merge-two-binary-trees/description/)，那么其结束条件要将两棵树都是null，某一棵为null的一共三种条件都作为结束条件才行。
- 一开始几乎都是判断null的操作，原因不仅是第一次循环之中如果为null那么直接返回，更重要的是null意味着判断到了最下层的节点，如果判断到了最下层的节点依旧找不到值，那么通常是返回失败。
136.Single Number
https://leetcode.com/problems/single-number/
本题精彩之处在于要求时间复杂度O(n),而且要求不可以使用额外空间，空间复杂度为O(1)。这就断了我们使用排序或者是hashMap来解决的路。本题之中使用二进制异或的性质来完成，所有数字异或之后就是结果。
为什么可以用异或来完成数字之间的比较？
- 0和任何数异或都是其本身，那么我们就可以使用0作为函数的初始条件。
- 任何数和本身异或都是0， 那么两个相同的数异或之后可以抵消。
先说下这个抵消的问题：
计算机之中都是使用二进制的，我们来做个示例就知道这种抵消效应了：
假设为[6,2,6],那么
6=0110
2=0010
6 ^ 2 = 0100 = 4
0100 ^ 6 = 0100 ^ 0110 = 0010 = 2
你看，回来了不是。
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for(int i :nums){
result = result ^ i;
}
return result;
}
}
513. Find Bottom Left Tree Value
本题之中我认为最有趣的是其活用了Queue的先入先出后入后出的性质。通过每次入队时候先入右边节点再入左边节点，那么最后剩下的一定是“最底层的最左边的节点”。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode node = new TreeNode(root.val);
while(!queue.isEmpty()){
node = queue.poll();
if(node.right!=null) queue.add(node.right);
if(node.left!=null) queue.add(node.left);
}
return node.val;
}
}
637. Average of Levels in Binary Tree
https://leetcode.com/problems/average-of-levels-in-binary-tree/
本题的亮点在于其不需要另外一个ArrayList来存储每一层之中的节点，而是可以通过控制遍历时候的长度来实现分层的作用。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
ArrayList<Double> list = new ArrayList<>();
if(root == null) return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
double num = 0;
int length = queue.size();
for(int i=0;i<length;i++){
TreeNode item = queue.poll();
num+=item.val;
if(item.left!=null) queue.add(item.left);
if(item.right!=null) queue.add(item.right);
}
num = num/length;
list.add(num);
}
return list;
}
}
