局部变量和参数，定义出来的放在stack里面

TreeNode node = new TreeNode(10)

node在stack，new出来的在heap

根据时间复杂度倒退算法：

O(1) 极少

O(logn) 二分法

O(根号n) 分解质因数

O(n) 高频

O(nlogn) 排序

O(n^2) 数组，枚举，动态规划

O(n^3) 数组，枚举，动态规划

O(2^n) 组合有关的搜索

O(n!)  排序有关的搜索

DFS： 1.非递归

2.递归 ： 1.traverse

2.divide and conquer

Binary tree非递归

0.preorder

   思想：one tree is composed of 3 part: root, all left, all right;

   一棵树可以看成只有一个当前点，其他所有子节点都是左或者右孩子。

   所以preorder分3步：

    1. root 入stack判断非空

    2. 右孩子入栈

    3. 左孩子入栈

public List<Integer> preorderTraversal(TreeNode root) {

Stack<TreeNode> stack = new Stack<TreeNode>();

List<Integer> preorder = new ArrayList<Integer>();

if (root == null) {

return preorder;

}

stack.push(root);

while (!stack.empty()) {

TreeNode node = stack.pop();

preorder.add(node.val);

if (node.right != null) {

stack.push(node.right);

}

if (node.left != null) {

stack.push(node.left);

}

}

return preorder;

}

inorder:

  1.找到最左边的点，过程中将所有点入Stack，返回并指向右孩子

  2.返回到他的父节点，返回并指向右孩子，

  循环

public ArrayList<Integer> inorderTraversal(TreeNode root) {

Stack<TreeNode> stack = new Stack<TreeNode>();

ArrayList<Integer> result = new ArrayList<Integer>();

TreeNode curt = root;

while (curt != null || !stack.empty()) {

while (curt != null) {

stack.add(curt);

curt = curt.left;

}

curt = stack.peek();

stack.pop();

result.add(curt.val);

curt = curt.right;

}

return result;

}

postOrder:

public List<Integer> postorderTraversal(TreeNode root) {

LinkedList<Integer> ans = new LinkedList<>();

Stack<TreeNode> stack = new Stack<>();

if (root == null) return ans;

stack.push(root);

while (!stack.isEmpty()) {

TreeNode cur = stack.pop();

ans.addFirst(cur.val);

if (cur.left != null) {

stack.push(cur.left);

}

if (cur.right != null) {

stack.push(cur.right);

}

}

return ans;

}

递归的方法

1.traverse（ 一个人干活））

以前序遍历为例子：

3要素：

1.递归的定义：把root为根的前序遍历放进result traverse(TreeNode root, ArrayList result){}//假设已经做好了

2.递归的拆分：穿进去的参数越来越小

3.递归的出口：结束条件（判断root == null）能解决大多问题

2.分治法：（小弟汇报）divide and conquer

1.递归的定义：求出root为根的preorder并return

2.递归的拆分：

3.递归的出口：

1.求max depth

用递归： int left = maxPathSum(root.left);

int right = maxPathSum(root.right);

return Math.max(left,right) + 1;

balanced binary tree: Left tree is balanced, right tree is balanced and heigh difference <= 1

2.求max value through a path in a tree -1 return -1

-2 -3

public int maxPathSum(TreeNode root)

if(root = null){

return Integer.MIN_VALUE;//负无穷大 因为找不到包含点的路径，如果求最小值return Integer.MAX_VALUE

}

int left = maxPathSum(root.left);

int right = maxPathSum(root.right);

if(Math.max(right,left) < 0){

return root.value;

}

else{

return Math.max(right,left) + root.value;

}

//或者更简单的写法

return Math.max(Math.max(left,right),0) + root.value;

3.从任意节点出发到任意节点结束： -3

-2 -1 return max return -1

1. 全在左边

2.全在右边

3.至少包含根节点

分为3部分

1.左边根节点到任意点

2.根节点

3。右边根节点到任意点

类似于上一题，所以需要两个值， root2any 和 any2any

private class ResultType{

int root2any, any2any;

ResultType(int root2any,int any2any){

this.any2any = any2any;

this.root2any = root2any;

}

}

private ResultType helper(TreeNode root){

if(root == null){

return new ResultType(Integer.MIN_VALUE,Integer.MIN_VALUE);

}

}

//Divide

ResultType left = helper(root.left)// 求得左边的root2any 和any2any

ResultType right = helper(root.right)//求得右边的

//conquer

//求得当前的点

int root2any = Math.max(0,Math.max(left.root2any,right.root2any)) + root.value

int any2any = Math.max(left.any2any,right.any2any);//在左边或右边

any2any = Mathmax(any2any,

Math.max(left.root2any,0) + root.value + Math.max(right.root2any,0));

return new ResultType(root2any, any2any);

public int maxPathSum(TreeNode node){

ResultType result = helper(root);

return result.any2any;

}

4.Binary Search Tree

1.左子树 < root

2.right >= root

3. in- order traversal 升序

4.in-order 不是升序的一定不是BST

5.中序遍历是升序不一定是BST

  5. lowest common ancestor 二叉树

   问题先给left做，再给right做，别自己做

6.Max average sub tree

/**和path，Minimum Subtree这类题差不多，

* 这一类的题目都可以这样做：

* 开一个ResultType的变量result，

* 来储存拥有最大average的那个node的信息。

* 然后用分治法来遍历整棵树。

* 一个小弟找左子数的average，一个小弟找右子树的average。

* 然后通过这两个来计算当前树的average。

* 同时，我们根据算出来的当前树的average决定要不要更新result。

* 当遍历完整棵树的时候，

* result里记录的就是拥有最大average的子树的信息。*/

7. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

两种情况：1.左子树里或者右子树里

2.包裹了root

但是为了计算第二种情况，仅仅使用any2any还不够，因为是一条路，root不能和any2any连接，so，need anyother variable : root2any

BFS   重点： 用queue存放即将被检查的点。用HashSet存放已经连接着的点

能用BFS就就BFS，别用DFS，因为会stack over flow，如果深度太深。

因为BFS用的是heap空间，虽然BFS更耗空间，但是heap很大。 DFS耗费的是stack空间，只有8M很小

使用：图遍历：1.层级遍历2.由点到面3.拓扑排序

最短路径问题：1.简单图求最短路径（边长为1没方向）

最长路径不能用BFS

二叉树的BFS：  时间复杂度O(E) E就是边 在二叉树里因为点和边一样多，所以是O(n)

1.起点丢到队列里（Queue）

Queue.isEmpty() Queue.size() Queue.poll() Queue.offer() 记住

因为queue的size会变，所以记住用size = Queue.size()先保存下来再循环

2.while(Q不空) {

for循环当前层所有节点，现将当前层节点删掉，再将所有子节点放进Queue里面去

}

二叉树序列化 #代表空的位置

判断可能重复进入队列的点，用hashmap

用这样的来表示图的一个点 Map<Integer,Set<Integer>> graph = new HashMap<>();//Set就是只有key没有value

判断图是否是树的问题：首先树的定义：边比点小1，点都联通。

所以可以用BFS，从一个点开始，看是否能找到所有的点

1.先用HashMap来表示这个图 Map<Integer,Set<Integer>> graph = new HashMap<>()

private Map<Integer,Set<Integer>> initialGraph(int n, int[][] edges) {

Map<Integer,Set<Integer>> result = new HashMap<>();

for (int i = 0; i < n; i++) {

          result.put(i,new HashSet<Integer>());//所有点加进去

      }

      for (int i = 0; i < edges.length; i++) {//每一个边遍历，将邻居加进去

         bian int u = edges[i][0];

int v = edges[i][1];

result.get(u).add(v);

result.get(v).add(u);

}

return result;

}

2.判断满足条件：

if (n == 0 || n - edges.length != 1) {

return false;

}

3.用queue存放即将被检查的点

用HashSet存放连接着的点

4.最后检查HashSet的size是不是和n一样，一样则说明是tree

Topological sorting

有向图，

不用DFS的做法，用BFS的做法

1.把入度为0的点丢到待学习的空间中

2.相邻的点入度更新

所以先要用HashMap统计每个点的入度

然后把没有入度的点放到queue

遍历queue，把点拿出来放到result里，所有邻居入度-1，减到0的时候加到queue里

看下result长度和graph长度是否相等，相等说明拿完了，不相等说明不能做完拓扑排序。

矩阵中宽度优先搜索：

图： N点M个边

M最大是N**2

时间复杂度是O(N+M) 一般M更大

矩阵：

R行C列

R*C个点 O(R*C*2)个边，因为一个点上下左右4边，每个边被两个点共享

时间复杂度O(R*C)

数岛屿用灌水法，把他和相连的1都变成0

看你灌水几次就是几个岛屿

僵尸问题需要层级遍历

需要两句话： int size = queue.size();

for (int i = 0; i < size; i ++)

DFS

1.Resursion

2.combination

3.permutation

4.Graph

5.Non-Recusion

什么时候用：

求所有组合的时候，90%是2 或者3

回文切割问题， n 个字母就是相当于n-1个的组合问题

abc : a b c ->[1,2]

a bc - >[1]

ab c ->[2]

abc ->[]