二、二叉树

1. 概述

• 定义：对一般的树加了约束：

• 每个结点最多两棵子树，即二叉树中不存在 度大于2 的结点

• 子树有 左右次序 之分

• 有 5 种形态：

• 满二叉树和完全二叉树（对满二叉树最底层，从右至左删除结点）

2. 重要特性

• 二叉树，在第 i 层至多有 2i-1 个结点
• 深度为 k 的二叉树至多有 2k-1 个结点
• 高度（或深度）为 K 的完全二叉树至少有 2k-2 个 叶子结点
• 非空二叉树的 叶子结点数 等于度为 2 的结点数加 1，即：n0 = n2 + 1

完全二叉树的 n1 只能是 0 或者 1

• 一颗度为 m 的二叉树，度为 1 的结点为 n1，度为 2 的结点为 n2，… …，度为 m 的结点数为 nm，则叶子结点数：n0**= 1 + n2****+ 2n3****+…+ (m-1)nm**
• 具有 n 个结点的完全二叉树，深度为 log2n + 1
• 编号性质：n 个结点的完全二叉树（其深度为 log2n + 1），对各结点从上到下，从左到右依次编号（1~n）则：若 i 是某结点 a 的编号：
• 如果 i 不等于 1，则 a 的双亲结点的编号为： ⌊ i/2 ⌋
• 如果 2i ≤ n, 则 a 的左孩子编号为 2i；如果** 2i > n**, 则 a** 无左孩子**；
• 如果** 2i + 1 ≤ n**, 则 a 的右孩子编号为** 2i + 1**；如果** 2i + 1> n**, 则 a** 无右孩子**；

三、二叉树的存储结构

1. 顺序存储

• 用 数组 来存储数据元素
• 从存储的角度来看，这种顺序存储结构，仅适用于 完全二叉树

因为在最坏的情况下，一个深度为 k 且只有 k 个结点的单支树( 树中不存在度为 2 的结点 )，却需要长度为 2k-1 的一维数组。

2. 链式存储

• 以 链表 的形式，存储数据元素以及数据元素之间的关系。

四、二叉树的遍历

1. 由遍历序列确定二叉树

• 由 先序和中序，可以确定
• 由 后序和中序，可以确定（但是注意后序最后一个为根，下一个是右子树根）
• 由 层次和中序，可以确定

2. 根据遍历序列估计二叉树

• 前序 遍历序列 和 后序 遍历序列 相同 的树：只有根结点
• 前序 遍历 和 中序 遍历 相同 的二叉树：所有结点没有左子树（右单分支树
• 中序 遍历 和 后序 遍历 相同 的二叉树：所有结点没有右子树（左单分支树）
• 前序遍历 和 后序 遍历 相反 的二叉树：没有左子树或者没有右子树（只有一个叶子结点）高度等于其结点数
• 前序 遍历 和 中序 遍历 相反 的二叉树：所有结点没有右子树（左单分支树）
• 中序 遍历 和 后序 遍历 相反 的二叉树：所有结点没有左子树（右单分支树）

3. 遍历和建树代码

• 二叉树的建树
• 深度优先遍历（先序，中序和后序）
• 广度优先遍历（先序，后序）

/* BitTree.java */

package com.java.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Jaco.Young.
 * 2018-06-13 18:26
 */
public class BitTree {

    //代表由先序和中序唯一确定的树的根结点
    private TreeNode root;

    /**
     * 提供给外部调用的方法
     * 字符数组pre表示先序遍历序列，mid表示中序遍历序列
     */
    public void build(char[] pre, char[] mid){
        //将创建树的根结点赋值给 root
        root = buildTree(pre,0, pre.length-1, mid, 0, mid.length-1);
    }

    /**
     * 前提条件，树中不存在重复元素
     * 由先序遍历序列和中序遍历序列，构造二叉树的方法
     * 我们建树的过程总是将序列不断地分割成左子树、右子树
     * lPre、rPre和lMid、rMid，分别就表示要对先序和中序的哪一部分进行建树
     */
    private TreeNode buildTree(char[] pre, int lPre, int rPre, char[] mid, int lMid, int rMid){
        //在先序遍历序列中，找到当前这棵树的根结点
        char root = pre[lPre];

        //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置
        int rootIndex = getRootIndex(mid, lMid, rMid, root);

        //如果没有找到，说明所给的参数异常
        if(rootIndex == -1){
            throw new IllegalArgumentException("Illegal Argument!");
        }

        //计算当前这棵树，左右子树的个数
        //整个中序序列：[左子树(lMid)  root(rootIndex)  右子树(rMid)]
        //左子树[lMid,rootIndex-1]
        int lNum = rootIndex - lMid; //rootIndex-1 -lMid + 1
        //右子树[rootIndex+1,rMid]
        int rNum = rMid - rootIndex;  //rMid - (rootIndex + 1) + 1

        //开始构建当前根结点的左子树和右子树
        //先构建左子树
        TreeNode lchild;  //作为左子树的根结点
        //以当前结点为根的树，没有左子树
        if(lNum == 0){
            lchild = null;
        }else{
            //当前这个树的左子树，仍然是一棵树，递归构造这棵树的左子树
            //设x为当前树先序中左子树最后一个元素的下标，则：x - (lpre + 1) = lNum
            //得：x = lPre + lNum
            lchild = buildTree(pre, lPre + 1, lPre+lNum, mid, lMid, rootIndex - 1);
        }

        //构建右子树
        TreeNode rchild;
        if(rNum == 0){
            rchild = null;
        }else{
            //当前结点的右子树，仍然包含很多节点，需要递归的构造其右子树
            rchild = buildTree(pre, lPre + lNum + 1, rPre, mid, rootIndex + 1, rMid);
        }

        //构造完整的二叉树
        return new TreeNode(root,lchild,rchild);
    }

    //在中序遍历序列中，根据先序中的根结点来查找在中序中的位置
    private int getRootIndex(char[] mid, int lMid, int rMid, char root) {
        for(int i = lMid; i <= rMid; i++){
            if(mid[i] == root){
                return i;
            }
        }
        return -1;
    }

    //二叉树每一个结点的结构
    private class TreeNode{
        //结点中存储的数据
        char item;
        //指向左孩子结点


> **Java网盘：pan.baidu.com/s/1MtPP4d9Xy3qb7zrF4N8Qpg
> 提取码：2p8n**



### 最后

毕竟工作也这么久了 ，除了途虎一轮，也七七八八面试了不少大厂，像阿里、饿了么、美团、滴滴这些面试过程就不一一写在这篇文章上了。我会整理一份详细的面试过程及大家想知道的一些问题细节

### 美团面试经验
![美团面试](https://www.www.zyiz.net/i/ll/?i=img_convert/120428b3297bdceb312b567878d65d5e.png)
字节面试经验
![字节面试](https://www.www.zyiz.net/i/ll/?i=img_convert/0dc1f994d7c60586500c1b3e58f38e38.png)
菜鸟面试经验
![菜鸟面试](https://www.www.zyiz.net/i/ll/?i=img_convert/1c48323a4391f12b5f2c4eb96390de0d.png)
蚂蚁金服面试经验
![蚂蚁金服](https://www.www.zyiz.net/i/ll/?i=img_convert/e91964dd4ec9dc679a77da2d0da2bb0e.png)
唯品会面试经验
![唯品会](https://www.www.zyiz.net/i/ll/?i=img_convert/8f24d4bf51040f428ec2f4763d1754a5.png)

>因篇幅有限，图文无法详细发出
>
>**[CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](

)**

631407720281)]
蚂蚁金服面试经验
[外链图片转存中...(img-mKzl7NVe-1631407720282)]
唯品会面试经验
[外链图片转存中...(img-x4YTi4zo-1631407720282)]

>因篇幅有限，图文无法详细发出
>
>**[CodeChina开源项目：【一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频】](

)**