LinkedList（链表）是特殊化的Tree Tree是特殊化的Grape（图）
二叉搜索树的复杂度一般是O（log n）增加叶子 搜索叶子 删除叶子都是O（log n）
二叉树的遍历：前序：根左右 中序：左根右 后续：左右根
树的面试题的解法一般都是递归
树的定义（背下来）
public class TreeNode{
intval;
TreeNodeleft;
TreeNoderight;
TreeNode(intx){
val=x;}
}
树节点的定义：（背下来）
public class TreeNode{
publicint val;
publicTreeNode left,right;
publicTreeNode(int val){
this.val=val; this.left=null; this.right=null;}
}
二叉树的中序遍历（用递归法来做） O(1)
class Solution{
publicList inorderTraversal(TreeNode root){ root是左中右三个节点
List<Integer>res=new ArrayList<>();
if(root!=null) inorder(root,res); 节点不是空的 就带上一个空的res扔给inorder returnres;
}
publicvoid inorder(TreeNode root,List res){
if(root.left!=null) inorder(root.left,root); inorder方法内的规则就是正常三种顺序遍历的规则 res.add(root.val); if(root.right!=null) inorder(root.right,res)}
}
递归的中心结构：(java代码实现 要背下来)
public void recur(int level,int param){
if(level>MAX_LEVEL){ return;} 1.recursion terminator 递归终结条件
process(level,param); 2.process logic in current level 处理当前层逻辑
recur(level:level+1,newParam); 3.drill down 下探到下一层
4.reverse the current level status if needed清理当前层
}
括号生成（递归法）
class Sulution{
private List res;
public List generateparenthesis(int n){
res=new ArrayList();
_generate(0,0,n,""); 0是左右括号初始个数 n是输入几个数字 空集合
return res;
}
private void _generate(int left,int right,int n,String s){
if(leftn&&rightn){ res.add(s); return res; } 当左右括号都用完n的次数时 加入左右括号 到集合res
if(left<n) _genarate (left+1,right,n,s+"(" ); 如果左括号不够n 那就加左括号
if(left<right) _generate(left,right+1,n,s+")"); 右括号没有左面的多 就加右括号
}
}
