二叉树那些事儿

摘要：大家在聊到二叉树的时候，总会离不开链表。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。存储结构线性表主要由顺序表示或链式表示。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。

大家在聊到二叉树的时候，总会离不开链表。这里先带大家一起了解一些基本概念。

线性表是最基本、最简单、也是最常用的一种数据结构。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。

1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有 唯一的后继(后件)。
4．除第一个元素之外，均有 唯一的前驱(前件)。

线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。

顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像，称为结点（node）。它包括两个域；存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

存储数据元素的数据域

存储下一个结点地址的指针域。

链表不必须按顺序存储，链表在插入的时候可以达到O(1)的时间复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表结点声明如下：

class ListNode
{
    let nodeValue; //数据
    let next; //指向下一个节点的指针

};

从内存角度出发： 链表可分为 静态链表、动态链表。
从链表存储方式的角度出发：链表可分为 单向链表、双向链表、以及循环链表。

把线性表的元素存放在数组中，这些元素可能在物理上是连续存放的，也有可能不是连续的，它们之间通过逻辑关系来连接，数组单位存放链表结点，结点的链域指向下一个元素的位置，即下一个元素所在的数组单元的下标。显然静态链表需要数组来实现。
引出的问题：数组的长度定义的问题，无法预支。

改善了静态链表的缺点。它动态的为节点分配存储单元。当有节点插入时，系统动态的为结点分配空间。在结点删除时，应该及时释放相应的存储单元，以防止内存泄露。

单链表是一种顺序存储的结构。有一个头结点，没有值域，只有连域，专门存放第一个结点的地址。有一个尾结点，有值域，也有链域，链域值始终为NULL。所以，在单链表中为找第i个结点或数据元素，必须先找到第i - 1 结点或数据元素，而且必须知道头结点，否者整个链表无法访问。

循环链表，类似于单链表，也是一种链式存储结构，循环链表由单链表演化过来。单链表的最后一个结点的链域指向NULL，而循环链表的建立，不要专门的头结点，让最后一个结点的链域指向链表结点。

循环链表与单链表的区别

链表的建立。单链表需要创建一个头结点，专门存放第一个结点的地址。单链表的链域指向NULL。而循环链表的建立，不要专门的头结点，让最后一个结点的链域指向链表的头结点。

链表表尾的判断。单链表判断结点是否为表尾结点，只需判断结点的链域值是否是NULL。如果是，则为尾结点；否则不是。而循环链表盘判断是否为尾结点，则是判断该节点的链域是不是指向链表的头结点。

双链表也是基于单链表的，单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表则是添加了一个链域。通过两个链域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。但是双链表还是不够灵活，在实际编程中比较常用的是循环双链表。但循环双链表使用较为麻烦。

求单链表中结点的个数
这是最最基本的了，应该能够迅速写出正确的代码，注意检查链表是否为空。时间复杂度为O（n）。参考代码如下：

function GetListLength(head)  
{  
    if(head === NULL) return 0;  
    let len = 0;  
    let current = head;  // ListNode
    while(current !== NULL)  
    {  
        len++;  
        current = current.next;  
    }  
    return len;  
} 

将单链表反转
从头到尾遍历原链表，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的情况。时间复杂度为O（n）。参考代码如下

// 反转单链表  
function ReverseList(ListNode head)  
{  
    // 如果链表为空或只有一个结点，无需反转，直接返回原链表头指针  
    if(head === NULL || head.next === NULL) return head;  
    let prev = NULL; // ListNode 反转后的新链表头指针，初始为NULL  
    let current = head;  
    while(current !== NULL)  
    {  
        let temp = current;  //获取当前节点ListNode
        current = current.next;  //获取下一个节点
        temp.next = prev; // 将当前结点摘下，插入新链表的最前端  
        prev = temp;  //上一个节点前进一位
    }  
    return prev;  
}

已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
这个类似归并排序。尤其注意两个链表都为空，和其中一个为空时的情况。只需要O（1）的空间。时间复杂度为O（max(len1, len2)）。参考代码如下：

// 合并两个有序链表  
function MergeSortedList(head1, head2)
{  
    if(head1 == NULL) return head2;  
    if(head2 == NULL) return head1;  
    let headMerged = NULL;  
    if(head1.nodeValue < head2.nodeValue)  
    {  
        headMerged = head1;  
        headMerged.next = MergeSortedList(head1.next, head2);  
    }  
    else  
    {  
        headMerged = head2;  
        headMerged.next = MergeSortedList(head1, head2.next);  
    }  
    return headMerged;  
} 

判断一个单链表中是否有环
这里也是用到两个指针。如果一个链表中有环，也就是说用一个指针去遍历，是永远走不到头的。因此，我们可以用两个指针去遍历，一个指针一次走两步，一个指针一次走一步，如果有环，两个指针肯定会在环中相遇。时间复杂度为O（n）。参考代码如下：

function HasCircle(head)  
{  
    let pFast = head; // 快指针每次前进两步  
    let pSlow = head; // 慢指针每次前进一步  
    while(pFast != NULL && pFast.next != NULL)  
    {  
        pFast = pFast.next.next;  
        pSlow = pSlow.next;  
        if(pSlow == pFast) // 相遇，存在环  
            return true;  
    }  
    return false;  
}

判断两个单链表是否相交
如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。
先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。参考代码如下：

function IsIntersected(head1, head2)  
{  
    if(pHead1 == NULL || pHead2 == NULL) return false;  
    let pTail1 = head1;  // 用来存储第一个链表的最后一个节点
    while(pTail1.next != NULL) { 
        pTail1 = pTail1.next; 
    } 
  
    let pTail2 = head2;  // 用来存储第二个链表的最后一个节点
    while(pTail2.next != NULL) {  
        pTail2 = pTail2.next; 
    } 
    return pTail1 == pTail2;  
} 

查找单链表中的倒数第K个结点（k > 0）
主要思路就是使用两个指针，先让前面的指针走到正向第k个结点，这样前后两个指针的距离差是k-1，之后前后两个指针一起向前走，前面的指针走到最后一个结点时，后面指针所指结点就是倒数第k个结点。
参考代码如下：

// 查找单链表中倒数第K个结点  
function GetRKthNode(head, k)
{  
    if(k == 0 || head == NULL) // 这里k的计数是从1开始的，若k为0或链表为空返回NULL  
        return NULL;  
  
    let pAhead = head;  
    let pBehind = head;  
    while(k > 1 && pAhead != NULL) // 前面的指针先走到正向第k个结点  
    {  
        pAhead = pAhead.next;  
        k--;  
    }  
    if(k > 1 || pAhead == NULL)     // 结点个数小于k，返回NULL  
        return NULL;  
    while(pAhead.next != NULL)  // 前后两个指针一起向前走，直到前面的指针指向最后一个结点  
    {  
        pBehind = pBehind.next;  
        pAhead = pAhead.next;
    }  
    return pBehind;  // 后面的指针所指结点就是倒数第k个结点  
} 

查找单链表的中间结点
此题可应用于上一题类似的思想。也是设置两个指针，只不过这里是，两个指针同时向前走，前面的指针每次走两步，后面的指针每次走一步，前面的指针走到最后一个结点时，后面的指针所指结点就是中间结点，即第（n/2+1）个结点。注意链表为空，链表结点个数为1和2的情况。时间复杂度O（n）。参考代码如下：

// 获取单链表中间结点，若链表长度为n(n>0)，则返回第n/2+1个结点  
function GetMiddleNode(head)  
{  
    if(head == NULL || head.next == NULL) // 链表为空或只有一个结点，返回头指针  
        return head;  
  
    let pAhead = head;  
    let pBehind = head;  
    while(pAhead.next != NULL) // 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步  
    {  
        pAhead = pAhead.next;  
        pBehind = pBehind.next;  
        if(pAhead.next != NULL)  
            pAhead = pAhead.next;  
    }  
    return pBehind; // 后面的指针所指结点即为中间结点  
} 

反转双向链表

function reverse(head){
    let cur = null;
    while(head != null){
        cur = head;
        head = head.next;
        cur.next = cur.prev;
        cur.prev = head;
    }
    return cur;
}

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

每个结点最多有两棵子树，所以二叉树中不存在大于2的结点。二叉树中每一个节点都是一个对象，每一个数据节点都有三个指针，分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。如下图所示：

完全二叉树是指最后一层左边是满的，右边可能满也可能不满，然后其余层都是满的。一个深度为k，节点个数为 2^k - 1 的二叉树为满二叉树（完全二叉树）。就是一棵树，深度为k，并且没有空位。

完全二叉树的特点有：

叶子结点只能出现在最下两层。

最下层的叶子一定集中在左部连续位置。

倒数第二层，若有叶子结点，一定都在右部连续位置。

如果结点度为1，则该结点只有左孩子。

同样结点树的二叉树，完全二叉树的深度最小。

是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历有三种方式，如下：
前序遍历：
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
中序遍历：
若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
后序遍历：
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

二叉查找树（BST）由节点组成，所以我们定义一个Node节点对象如下：

function Node(data,left,right){
    this.data = data;
    this.left = left;//保存left节点链接
    this.right = right;
    this.show = show;
}


function show(){
    return this.data;//显示保存在节点中的数据
}

查找最大和最小值
查找BST上的最小值和最大值非常简单，因为较小的值总是在左子节点上，在BST上查找最小值，只需遍历左子树，直到找到最后一个节点

function getMin(){
    var current = this.root;
    while(!(current.left == null)){
        current = current.left;
    }
    return current.data;
}

function getMax(){
    var current = this.root;
    while(!(current.right == null)){
        current = current.right;
    }
    return current.data;
}

递归解法：
（1）如果二叉树为空，节点个数为0
（2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
参考代码如下：

function GetNodeNum(pRoot)  
{  
    if(pRoot == NULL) return 0;  
    return GetNodeNum(pRoot->m_pLeft) + GetNodeNum(pRoot->m_pRight) + 1;  
} 

递归解法：
（1）如果二叉树为空，二叉树的深度为0
（2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
参考代码如下：

function GetDepth(pRoot)  
{  
    if(pRoot == NULL) return 0;  
    let depthLeft = GetDepth(pRoot->m_pLeft);  
    let depthRight = GetDepth(pRoot->m_pRight);  
    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);   
} 

前序遍历递归解法：
（1）如果二叉树为空，空操作
（2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树
参考代码如下：

function PreOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    Visit(pRoot); // 访问根节点  
    PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树  
    PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树  
}

中序遍历递归解法
（1）如果二叉树为空，空操作。
（2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树
参考代码如下：

function InOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树  
    Visit(pRoot); // 访问根节点  
    InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树  
} 

后序遍历递归解法
（1）如果二叉树为空，空操作
（2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点
参考代码如下：

function PostOrderTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    PostOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树  
    PostOrderTraverse(pRoot->m_pRight); // 后序遍历右子树  
    Visit(pRoot); // 访问根节点  
}

相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。

function LevelTraverse(pRoot)  
{  
    if(pRoot == NULL) return;  
    queue q;  
    q.push(pRoot);  
    while(!q.empty())  
    {  
        BinaryTreeNode * pNode = q.front();  
        q.pop();  
        Visit(pNode); // 访问节点  
        if(pNode->m_pLeft != NULL)  
            q.push(pNode->m_pLeft);  
        if(pNode->m_pRight != NULL)  
            q.push(pNode->m_pRight);  
    }  
    return;  
} 

要求不能创建新节点，只调整指针。
递归解法：
（1）如果二叉树查找树为空，不需要转换，对应双向链表的第一个节点是NULL，最后一个节点是NULL
（2）如果二叉查找树不为空：
如果左子树为空，对应双向有序链表的第一个节点是根节点，左边不需要其他操作；
如果左子树不为空，转换左子树，二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点，同时将根节点和左子树转换后的双向有序链表的最后一个节点连接；
如果右子树为空，对应双向有序链表的最后一个节点是根节点，右边不需要其他操作；
如果右子树不为空，对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点，同时将根节点和右子树转换后的双向有序链表的第一个节点连 接。
参考代码如下：

/*******************************************************************
参数： 
pRoot: 二叉查找树根节点指针 
pFirstNode: 转换后双向有序链表的第一个节点指针 
pLastNode: 转换后双向有序链表的最后一个节点指针 
*******************************************************************/  
function Convert(BinaryTreeNode * pRoot,   
             BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)  
{  
    BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;  
    if(pRoot == NULL)   
    {  
        pFirstNode = NULL;  
        pLastNode = NULL;  
        return;  
    }  
  
    if(pRoot->m_pLeft == NULL)  
    {  
        // 如果左子树为空，对应双向有序链表的第一个节点是根节点  
        pFirstNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);  
        // 二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点  
        pFirstNode = pFirstLeft;  
        // 将根节点和左子树转换后的双向有序链表的最后一个节点连接  
        pRoot->m_pLeft = pLastLeft;  
        pLastLeft->m_pRight = pRoot;  
    }  
  
    if(pRoot->m_pRight == NULL)  
    {  
        // 对应双向有序链表的最后一个节点是根节点  
        pLastNode = pRoot;  
    }  
    else  
    {  
        Convert(pRoot->m_pRight, pFirstRight, pLastRight);  
        // 对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点  
        pLastNode = pLastRight;  
        // 将根节点和右子树转换后的双向有序链表的第一个节点连接  
        pRoot->m_pRight = pFirstRight;  
        pFirstRight->m_pLeft = pRoot;  
    }  
  
    return;  
}  

递归解法：
（1）如果二叉树为空或者k<1返回0
（2）如果二叉树不为空并且k==1，返回1
（3）如果二叉树不为空且k>1，返回左子树中k-1层的节点个数与右子树k-1层节点个数之和
参考代码如下：

function GetNodeNumKthLevel(pRoot, k)  
{  
    if(pRoot == NULL || k < 1) return 0;  
    if(k == 1) return 1;  
    let numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子树中k-1层的节点个数  
    let numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子树中k-1层的节点个数  
    return (numLeft + numRight);  
} 

不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。
递归解法：
（1）如果两棵二叉树都为空，返回真
（2）如果两棵二叉树一棵为空，另一棵不为空，返回假
（3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假
参考代码如下：

function StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)  
{  
    if(pRoot1 == NULL && pRoot2 == NULL) // 都为空，返回真  
        return true;  
    else if(pRoot1 == NULL || pRoot2 == NULL) // 有一个为空，一个不为空，返回假  
        return false;  
    let resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比较对应左子树   
    let resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比较对应右子树  
    return (resultLeft && resultRight);  
} 

递归解法：
（1）如果二叉树为空，返回真
（2）如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假

递归解法：
（1）如果二叉树为空，返回空
（2）如果二叉树不为空，求左子树和右子树的镜像，然后交换左子树和右子树
参考代码如下：

function Mirror(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL) // 返回NULL  
        return NULL;  
    BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子树镜像  
    BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子树镜像  
        // 交换左子树和右子树  
    pRoot->m_pLeft = pRight;  
    pRoot->m_pRight = pLeft;  
    return pRoot;  
}

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
有如下算法，按层次（从上到下，从左到右）遍历二叉树，当遇到一个节点的左子树为空时，则该节点右子树必须为空，且后面遍历的节点左右子树都必须为空，否则不是完全二叉树。

bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)  
{  
    if(pRoot == NULL)  
        return false;  
    queue q;  
    q.push(pRoot);  
    bool mustHaveNoChild = false;  
    bool result = true;  
    while(!q.empty())  
    {  
        BinaryTreeNode * pNode = q.front();  
        q.pop();  
        if(mustHaveNoChild) // 已经出现了有空子树的节点了，后面出现的必须为叶节点（左右子树都为空）  
        {  
            if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)  
            {  
                result = false;  
                break;  
            }  
        }  
        else  
        {  
            if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)  
            {  
                q.push(pNode->m_pLeft);  
                q.push(pNode->m_pRight);  
            }  
            else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)  
            {  
                mustHaveNoChild = true;  
                q.push(pNode->m_pLeft);  
            }  
            else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)  
            {  
                result = false;  
                break;  
            }  
            else  
            {  
                mustHaveNoChild = true;  
            }  
        }  
    }  
    return result;  
}