二叉树的特性

二叉树的特性 时间复杂度计算过程写一下
二叉树是一棵树，且每个节点都不能有多于两个的儿子，且二叉树的子树有左右之分，次序不能颠倒。

二叉树的性质
在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。
深度为k的二叉树至多有2^k - 1个节点（k>=1)。
对任何一棵二叉树T，如果其叶结点数目为n0，度为2的节点数目为n2，则n0=n2+1。
**满二叉树：**深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。

**完全二叉树：**深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。

具有n个节点的完全二叉树的深度为log2n + 1。

二叉搜索树，平衡二叉树，红黑树的算法效率
操作 二叉查找树 平衡二叉树 红黑树
查找 O(n) O(logn) Olog(n)
插入 O(n) O(logn) Olog(n)
删除 O(n) O(logn) Olog(n)
Olog(n)怎么算出来的
在一个树中查找一个数字，
第一次在根节点判断，第二次在第二层节点判断
以此类推，树的高度是多少就会判断多少次
树的高度和节点的关系就是以2为底，树的节点总数n的对数
. 手写二分 有序正负数组找到近 0 的两个数
public static int[] divide(int[] array){
int mid = (min + max) / 2;
int[] result = new int[2];
while(array[mid] != 0){
if(array[mid] > 0){
max = mid - 1;
}
if(array[mid] < 0){
min = mid + 1;
}
if(min >= max){
break;
}
mid = (min + max) / 2;
}
result[0] = array[mid - 1];
result[1] = array[mid + 1];
return result;
}
. 二叉树三种遍历：
public class TreeNode{
int val;
public TreeNode(va){
val = va;
}
TreeNode left;
TreeNode right;
}
前序遍历：(根左右)

/递归法/
ArrayList<Integer> pre = new ArrayList<>();
public ArrayList<Integer> DLR(TreeNode root){
if(root == null){
return pre;
}
pre.add(root.val);
DLR(root.left);
DLR(root.right);

return pre;
}
/*非递归法
、申请一个栈stack，然后将头节点压入stack中。

、从stack中弹出栈顶节点，打印，再将其右孩子节点（不为空的话）先压入stack中，最后将其左孩子节点（不为空的话）压入stack中。

、不断重复步骤2，直到stack为空，全部过程结束。*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<Integer>();
Stack<TreeNode> stack=new Stack<TreeNode>();
if (root!=null) {
stack.push(root);
while(!stack.empty()) {
TreeNode tr=stack.pop();
list.add(tr.val);
if(tr.right!=null) {
stack.push(tr.right);
}
if(tr.left!=null) {
stack.push(tr.left);
}
}
}
return list;
}
中序遍历：（左根右）

/递归法/
ArrayList<Integer> mid = new ArrayList<>();
public ArrayList<Integer> LDR(TreeNode root){
if(root == null){
return mid;
}
LDR(root.left);
mid.add(root.val);
LDR(root.right);

return mid;
}
/*非递归法
、申请一个栈stack，初始时令cur=head

、先把cur压入栈中，依次把左边界压入栈中，即不停的令cur=cur.left，重复步骤2

、不断重复2，直到为null，从stack中弹出一个节点，记为node，打印node的值，并令cur=node.right,重复步骤2

、当stack为空且cur为空时，整个过程停止。*/
public List<Integer> inorderTraversal(TreeNode head) {
List<Integer> list=new ArrayList<Integer>();
Stack<TreeNode> stack=new Stack<TreeNode>();
if (head!=null) {
while(head!=null||!stack.empty()) {
if(head!=null) {
stack.push(head);
head=head.left;
}else {
head=stack.pop();
list.add(head.val);
head=head.right;
}
}
}
return list;
}
后序遍历：（左右根）

/递归法/
ArrayList<Integer> post = new ArrayList<>();
public ArrayList<Integer> LRD(TreeNode root){
if(root == null){
return post;
}
LRD(root.left);
LRD(root.right);
post.add(root.val);

return post
}

/*非递归法
用非递归的方式实现后序遍历有点麻烦。

、申请一个栈s1，然后将头节点压入栈s1中。

、从s1中弹出的节点记为cur，然后依次将cur的左孩子节点和右孩子节点压入s1中。

、在整个过程中，每一个从s1中弹出的节点都放进s2中。

、不断重复步骤2和步骤3，直到s1为空，过程停止。

、从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。*/

public List<Integer> postorderTraversal(TreeNode head) {
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
if (head != null) {
stack1.push(head);
while(!stack1.empty()) {
head = stack1.pop();
stack2.push(head);
if (head.left != null) {
stack1.push(head.left);
}
if (head.right != null) {
stack1.push(head.right);
}
}
while(!stack2.empty()) {
list.add(stack2.pop().val);
}
}
return list;
}