链表：
1.引用对象
Link alink = someLink 和 Link someLine = new Link()
alink 和 someLine 都是对象的引用，他们指向内存中的同一个地方。只有new Link()才能创建一个新的对象。引用类型在创建之初就会被赋值为null。
2.first是一个只有指针没有值的，所以它不是第一个节点，而是内存区域存储引用的指针。first拥有对第一个链结点的引用。
- 链结点和链表
每个链结点（link对象）都包含一个对下一个链结点引用的字段next。链表本身的对象（LinkList），有一个字段指向第一个链结点的引用。
4.删除delete{
Link temp = first; //删除第一个节点之前，将它存储在temp变量中
first = first.next; //删除第一个节点
return temp; //返回temp值
}
出一个左孩子，访问一个，t=t.right使得t为null所以得进行一次外循环，这就使得再次pop一个，也就是pop了父节点
1.二叉树的遍历、层次遍历 2.节点数、深度 3.判断是否各种树
1.链表的反转 2.两个指针相关的操作 3.
package com.example.java;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class BinaryTree {
public int lastVal = Integer.MAX_VALUE;
public boolean firstNode = true;
//递归方式
//先序遍历
private ArrayList<Integer> preOrderReverse(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
preOrder(root, result);
return result;
}
private void preOrder(TreeNode root, ArrayList<Integer> result) {
if (root == null) {
return;
}
result.add(root.value);
preOrder(root.left, result);
preOrder(root.right, result);
}
//中序遍历
private void inOrderTraverse(TreeNode node) {
if (node == null)
return;
inOrderTraverse(node.left);
System.out.print(node.value);
inOrderTraverse(node.right);
}
//后序遍历: 左右根
private ArrayList<Integer> postOrder(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
//每次递归都new一个list,然后addAll
list.addAll(postOrder(root.left));
list.addAll(postOrder(root.right));
list.add(root.value);
return list;
}
//迭代，非递归方式
//先序遍历: 用栈来维持，先把根节点入栈并添加，然后依次放入右左节点，循环条件是栈不为空
public ArrayList<Integer> preOrder(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
list.add(node.value);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return list;
}
//中序遍历：左中右
public ArrayList<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
//只要根节点不为空，就依次向栈中添加左节点
while (node != null) {
stack.push(node);
node = node.left;
}
//出栈一个左节点，就保存一个
node = stack.pop();
list.add(node.value);
//node = node.right
//1.如果该node没有右子节点，使得node为null，所以得进行一次外循环，这就使得再次pop一个,也就是pop了父节点
//2.如果该node有右子节点，则把右子节点入栈，会走一遍里循环，变成 根-右的遍历。因为该node本来就是最左下节点
node = node.right;
}
return list;
}
//层级遍历：队列
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//边界条件
if (root == null) {
return result;
}
//创建的队列用来存放结点，泛型注意是TreeNode
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
//队列为空说明已经遍历完所有元素，while语句用于循环每一个层次
while (!queue.isEmpty()) {
int size = queue.size();
ArrayList<Integer> level = new ArrayList<>();
//也可以用while循环， while(count>0){最后count--;}
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll(); //相当于pop
level.add(node.value);
//区别：两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，
//add方法是抛出异常让你处理，而offer方法是直接返回false
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
//最大深度
private int maxDeath(TreeNode root) {
if (root == null) {
return 0;
}
int left = maxDeath(root.left);
int right = maxDeath(root.right);
//这个1指的是每次递归深度+1
return left > right ? left + 1 : right + 1;
}
//最小深度
private int getMinDepth(TreeNode root) {
if (root == null) {
return 0;
}
return getMin(root);
}
private int getMin(TreeNode root) {
if (root == null) {
return Integer.MAX_VALUE;
}
if (root.left == null && root.right == null) {
return 1;
}
return Math.min(getMin(root.left), getMin(root.right)) + 1;
}
//节点数
private int count(TreeNode root) {
if (root == null) {
return 0;
}
int left = count(root.left);
int right = count(root.right);
//这个1指的是本次递归的根节点
return left + right + 1;
}
//叶子节点
//如果某个节点有左子节点，没有右子节点，则该节点左右子节点数相加，并且进入下次递归1+0
//递归后的每次结果，相当于只有两种情况，要不为0，要不为1。本次的左右子节点就是下次的根节点
private int countLeaf(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return countLeaf(root.left) + countLeaf(root.right);
}
//第K层节点数
//1.输入输出是什么； 2.特殊的情况，为空等 3.正常的情况
//给定K，每经过一层-1，k<1作为递归的停止条件之一
private int countK(TreeNode root, int k) {
if (root == null || k < 1) {
return 0;
}
if (k == 1) {
return 1;
}
int left = countK(root.left, k - 1);
int right = countK(root.right, k - 1);
return left + right;
}
boolean isBalanced(TreeNode node) {
return maxDeath2(node) != -1;
}
// 一棵BST定义为：
// 节点的左子树中的值要严格小于该节点的值。
// 节点的右子树中的值要严格大于该节点的值。
// 左右子树也必须是二叉查找树。
// 一个节点的树也是二叉查找树。
int maxDeath2(TreeNode node) {
if (node == null) {
return 0;
}
int left = maxDeath2(node.left);
int right = maxDeath2(node.right);
if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
return -1;
}
return Math.max(left, right) + 1;
}
//判断是否为镜像
boolean isMiror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) {
return true;
}
if (t1 == null || t2 == null) {
return false;
}
if (t1.value != t2.value) {
return false;
}
return isMiror(t1.left, t2.left) && isMiror(t1.right, t2.right);
}
public boolean isValidBST(TreeNode root) {
// write your code here
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (!firstNode && lastVal >= root.value) {
return false;
}
firstNode = false;
lastVal = root.value;
if (!isValidBST(root.right)) {
return false;
}
return true;
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int data) {
left = null;
right = null;
this.value = data;
}
}
}
网友评论