![Caloch开洛奇中文网[备案:豫ICP备18021211号-1]](/images/thumbs/0000007_app-logo-on-light.png){kind=logo}
https://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/#:~:text=Top%2010%20Algorithms%20for%20Coding%20Interview%20This%20post,Manipulation%2C%209%29%20Combinations%20and%20Permutations%2C%20and%2010%29%20Math.
二叉树/binary tree:
## 1. Leetcode – Binary Tree Preorder Traversal (Java)
### Preorder binary tree traversal is a classic interview problem. The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.
```
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> returnList = new ArrayList<Integer>();
if(root == null)
return returnList;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode n = stack.pop();
returnList.add(n.val);
if(n.right != null){
stack.push(n.right);
}
if(n.left != null){
stack.push(n.left);
}
}
return returnList;
}
}
```
## 1.1 Leetcode – Binary Tree Postorder Traversal (Java)
### Among preoder, inorder and postorder binary tree traversal problems, postorder traversal is the most complicated one.
### For example, for the following tree, the post order traversal returns {4, 6, 5, 2, 3, 1}.
### The order of "Postorder" is: left child -> right child -> parent node.
### Find the relation between the previously visited node and the current node
### Use a stack to track nodes
### As we go down the tree to the lft, check the previously visited node. If the current node is the left or right child of the previous node, then keep going down the tree, and add left/right node to stack when applicable. When there is no children for current node, i.e., the current node is a leaf, pop it from the stack. Then the previous node become to be under the current node for next loop. You can using an example to walk through the code
```
//Definition for binary tree
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> lst = new ArrayList<Integer>();
if(root == null)
return lst;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode prev = null;
while(!stack.empty()){
TreeNode curr = stack.peek();
// go down the tree.
//check if current node is leaf, if so, process it and pop stack,
//otherwise, keep going down
if(prev == null || prev.left == curr || prev.right == curr){
//prev == null is the situation for the root node
if(curr.left != null){
stack.push(curr.left);
}else if(curr.right != null){
stack.push(curr.right);
}else{
stack.pop();
lst.add(curr.val);
}
//go up the tree from left node
//need to check if there is a right child
//if yes, push it to stack
//otherwise, process parent and pop stack
}else if(curr.left == prev){
if(curr.right != null){
stack.push(curr.right);
}else{
stack.pop();
lst.add(curr.val);
}
//go up the tree from right node
//after coming back from right node, process parent node and pop stack.
}else if(curr.right == prev){
stack.pop();
lst.add(curr.val);
}
prev = curr;
}
return lst;
}
}
```
#### 1.2.1
#### Java Solution 2 - Simple!
#### This solution is simple, but note that the tree's structure gets changed since children are set to null.
```
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if(root==null) {
return res;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.peek();
if(temp.left==null && temp.right==null) {
TreeNode pop = stack.pop();
res.add(pop.val);
}
else {
if(temp.right!=null) {
stack.push(temp.right);
temp.right = null;
}
if(temp.left!=null) {
stack.push(temp.left);
temp.left = null;
}
}
}
return res;
}
```
## 2. Graph
### Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node.
### Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes.
```
//Define a GraphNode
class GraphNode{
int val;
GraphNode next;
GraphNode[] neighbors;
boolean visited;
GraphNode(int x) {
val = x;
}
GraphNode(int x, GraphNode[] n){
val = x;
neighbors = n;
}
public String toString(){
return "value: "+ this.val;
}
}
//Define a Queue
class Queue{
GraphNode first, last;
public void enqueue(GraphNode n){
if(first == null){
first = n;
last = first;
}else{
last.next = n;
last = n;
}
}
public GraphNode dequeue(){
if(first == null){
return null;
}else{
GraphNode temp = new GraphNode(first.val, first.neighbors);
first = first.next;
return temp;
}
}
}
//Breath First Search uses a Queue
public class GraphTest {
public static void main(String[] args) {
GraphNode n1 = new GraphNode(1);
GraphNode n2 = new GraphNode(2);
GraphNode n3 = new GraphNode(3);
GraphNode n4 = new GraphNode(4);
GraphNode n5 = new GraphNode(5);
n1.neighbors = new GraphNode[]{n2,n3,n5};
n2.neighbors = new GraphNode[]{n1,n4};
n3.neighbors = new GraphNode[]{n1,n4,n5};
n4.neighbors = new GraphNode[]{n2,n3,n5};
n5.neighbors = new GraphNode[]{n1,n3,n4};
breathFirstSearch(n1, 5);
}
public static void breathFirstSearch(GraphNode root, int x){
if(root.val == x)
System.out.println("find in root");
Queue queue = new Queue();
root.visited = true;
queue.enqueue(root);
while(queue.first != null){
GraphNode c = (GraphNode) queue.dequeue();
for(GraphNode n: c.neighbors){
if(!n.visited){
System.out.print(n + " ");
n.visited = true;
if(n.val == x)
System.out.println("Find "+n);
queue.enqueue(n);
}
}
}
}
}
```
### BFS,DFS,neighboring matrix as graph
```
public class Graph { //A, B, C,D, E, F
static int[][] graph = new int[][]{{0, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 0, 0},
{1, 1, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0},
{0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0}};
int[] help = new int[graph.length];//用来记录已经遍历过的元素
//DFS(深度优先遍历)同样适用于有向图 A->C->B->D->E->F 即 0->2->1->3->4->5
public void dfsTraversing(int node, int[][] graph) {
help[node]=1;
System.out.println(node);
for (int i = 0; i < graph[node].length; ++i) {
if (help[i]==0&&i != node&&graph[node][i]==1) {
dfsTraversing(i, graph);
}
}
}
//BFS(广度优先遍历)同样适用于有向图 A->C->D->B->E->F 即0->2->3->1->4->5
public void bfsTraversing(int[][] graph) {//主要从一个节点邻居开始
int[] queue=new int[graph.length];
int cnt=1;
queue[0]=0;//将A作为起始顶点加入队列
help[0]=1;
System.out.println(0);
for (int i=0;i<cnt;++i){//cnt 的上限呢? 应该小于节点的总数,cnt改为graph.length
for (int j=0;j<graph[queue[i]].length;++j){
if (queue[i]!=j&&graph[queue[i]][j]==1&&help[j]==0){
help[queue[i]]=1;
queue[cnt++]=j;
System.out.println(j);
}
}
}
}
}
```