二叉树

这周本来要期中考试的，结果几天前栖霞区出现了聚集性感染，又被迫线上课了，只好推迟考试，所以继续学习树相关的内容。我们目前学的树还仅限于二叉树，操作也只有创建、遍历两种，但实际上树的问题十分复杂，并且能由它引申出很多高级数据结构，比如前缀树、平衡树、红黑树、线段树……估计也不在这门课的学习范围内了吧（我也就略知一二，搜到板子会用而已）。

言归正传，这节课我们花了很多时间来讲先、中、后序遍历的非递归算法，以及树的#号表示法。

二叉树的遍历

不同于线性结构（数组、链表）中每个元素最多有一个前驱和一个后继，二叉树中每个元素可以有两个后继，这导致二叉树的遍历也有好几种方法，可以分为深度优先遍历和广度优先遍历两大类，而深度优先遍历根据父节点何时遍历又可以分为先序遍历、中序遍历、后序遍历，广度优先遍历也叫层序遍历。注意，不特别说明，所有的遍历都是自左向右的。

用一个例子来说明他们的差别：

二叉树遍历

先序遍历结果：ABDFKICEHJG

中序遍历结果：DBKFIAHEJCG

后序遍历结果：DKIFBHJEGCA

层序遍历结果：ABCDFEGKIHJ

注意，父节点的遍历顺序是针对左右子树的，而不是左右孩子，比如在中序遍历中，我们要将左子树遍历完，才轮得到父节点，而每一个子树都是如此，所以最先遍历的是左下角的那个节点。

这样的思想很自然地带着递归的感觉，所以用递归来写遍历算法是最简洁、最方便的，如果在算法竞赛这些赶时间的时候，肯定选择递归了，不过非递归的写法空间消耗小，因为自己维护的栈要比递归栈开销小，这是一种常数优化。而掌握遍历的非递归算法也是真正理解递归的一个证明，所以在学习的过程中，会重点讲非递归算法（也是因为递归算法太自然了，没什么可讲的），我是暑假时跟着邓俊辉老师的网课学的，当时云里雾里，想得多了，便也差不多理解了。

在进入遍历算法前，先亮出我的树节点的定义：

1
2
3
4
struct TreeNode{
    TreeNode *left=NULL,*right=NULL;//左右孩子指针
    int val=0;//值
};

深度优先遍历

先序遍历

先序遍历，就是遇到一棵树，先遍历根节点，然后分别遍历左右子树，这是方法和代码都最清晰的遍历方式了。

递归代码如下，没什么好说的：

1
2
3
4
5
6
7
8
void preOrderTrav(TreeNode *node)
{
    if(node==NULL)
        return ;
    visit(node);
    preOrderTrav(node->left);
    preOrderTrav(node->right);
}

先序遍历的非递归算法，其实也很好写。只需要每次取出栈顶，直接访问，然后将两个孩子入栈即可，注意，由于是先左后右访问，而栈是后入先出，所以应该先右后左入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void preOrderTrav(TreeNode *root)
{
    if(root==NULL)
        return ;
    stack<TreeNode*> stk;
    stk.push(root);
    while(!stk.empty())
    {
        TreeNode *node=stk.top();
        visit(node);
        stk.pop();
        if(node->right) stk.push(node->right);
        if(node->left) stk.push(node->left);
    }
    return ans;
}

然而，用这种方法来改写中序遍历和后序遍历，比较困难，因为父节点不能直接访问了，就不好控制访问的时机，比如说，在中序遍历时，只有左孩子被访问了，才能访问它，我们又如何得知左孩子的访问情况呢？如果捆绑一个标记，岂不是与我们的初衷“优化”背道而驰了吗。所以，我们要寻求一种新的方法。

注意到，在三种遍历中，都有一个顺左孩子而下的过程，先序遍历直接访问沿途节点，而中序、后序则是以此找到第一个访问的节点。我们以这种特性来重写非递归算法，在后面两种改写过程中会看到它的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void preOrderTrav(TreeNode *root)
{
    TreeNode *node = root;
    stack<TreeNode *> stk;
    while (true)
    {
        while (node)//visit along left branch
        {
            visit(node);//直接访问沿途节点
            stk.push(node);//入栈，这是为了保存它们的右子树
            node = node->left;
        }
        if (stk.empty())
            return ;
        node = stk.top()->right;//左子树遍历过了，访问右子树（逐层向上）
        stk.pop();
    }
    return ;
}

中序遍历

中序遍历，就是先访问左子树，左子树完全访问完了，访问父节点，然后访问右子树。

递归代码如下，只需要将先序遍历变换一下访问位置而已

1
2
3
4
5
6
7
8
void inOrderTrav(TreeNode *node)
{
    if(node==NULL)
        return ;
    inOrderTrav(node->left);
    visit(node);
    inOrderTrav(node->right);
}

而非递归算法，有了上面的铺垫，也就好写了。同样是先沿着左孩子向下，不过不直接访问，而是在出栈时访问，然后访问右子树。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void inOrderTrav(TreeNode *root)
{
    TreeNode *node = root;
    stack<TreeNode *> stk;
    while (true)
    {
        while (node)//visit along left branch
        {
            stk.push(node);//入栈
            node = node->left;
        }
        if (stk.empty())
            return ;
        visit(stk.top());//在出栈时访问它，然后访问它的右子树
        node = stk.top()->right;//左子树遍历过了，访问右子树（逐层向上）
        stk.pop();
    }
    return ;
}

后序遍历

后序遍历，就是依次访问左右子树，最后访问父节点。

递归代码如下：

1
2
3
4
5
6
7
8
void postOrderTrav(TreeNode *node)
{
    if(node==NULL)
        return ;
    postOrderTrav(node->left);
    postOrderTrav(node->right);
    visit(node);
}

而后序遍历的非递归算法，大体上与上面两个相似，然而要特别注意，访问父节点的标志是什么？既不是入栈时，也不是出栈时，而是右孩子被访问后，也就是说，与中序遍历相比，我们对栈顶多一个检验操作——如果右孩子被访问了，就访问并出栈，否则访问右孩子，方法是用一个pre指针记录前一个访问的节点是谁，只多出常数级别的消耗。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* node=root,*pre=NULL;
    while(true)//对每一个节点，我们先找到左下角的点并将沿途的点全部入栈，然后将右子节点作为新的根
    {
        while(node)//visitAlongLeftBranch
        {
            stk.push(node);
            node=node->left;
        }
        if(stk.empty())//为空，说明根节点完成了访问，结束
            return ;
        node=stk.top();
        if(node->right==NULL||pre==node->right)//如果右子树访问过了或者根本没有右子树，访问当前节点
        {
            visit(node);
            pre=node;
            stk.pop();
            node=NULL;
        }
        else
            node=node->right;//否则访问右子树节点入栈
    }
    return ;
}

层序遍历

层序遍历可以体现出二叉树的层次，也就是说，可以明确知道某个节点在哪一层，以及各层的情况，因而得名。大体上有dfs和bfs两种方式实现。

层次遍历是自上而下，自左而右的遍历顺序，因此bfs实现是比较直观的，dfs实现或许有些取巧——因为实际遍历顺序不是层序，只是能得出同样的结果而已。

深度优先遍历实现

由于深度优先遍历也有着自左而右的特点，我们只需要维护一个层数，并逐个添加结果即可，具体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> ans;
void preOrderTrav(TreeNode*node,int depth)//这里使用先序遍历的代码，其他两者也可以做
{
    if(node==NULL)
        return ;
    if(ans.size()>depth)
        ans[depth].push_back(node->val);
    else
        ans.push_back({node->val});
    preOrderTrav(node->left,depth+1);
    preOrderTrav(node->right,depth+1);
}
vector<vector<int>> levelOrderTrav(TreeNode* root) 
{
    preOrderTrav(root,0);
    return ans;
}

广度优先遍历实现

广度优先遍历，就要维护一个队列了，每次自左向右处理一层，并立即访问，然后将非空的孩子节点入队，直到队列为空。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> levelOrder(TreeNode* root) {
    if(root==NULL)
        return {};
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty())//每次处理一层
    {
        ans.push_back({});//添加一层
        int cnt=q.size();//当前q里面的全是上一层的，计数
        for(int i=1;i<=cnt;++i)//执行cnt次后，全是下一层的了
        {
            TreeNode* node=q.front();
            q.pop();
            ans.back().push_back(node->val);
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
    return ans;
}

二叉树的恢复

给我们怎样的信息，可以唯一确定一颗二叉树呢？应该有很多种组合，这里给出三种方法。

层序遍历序列(带null)

这种表示方法是把除叶节点外的每个节点都视为有两个孩子，进行层序遍历，如果事实上为空，就填null得到的序列。

这是比较清晰的，就像把整颗树画出来一样，具体可以参见297. 二叉树的序列化与反序列化 - 力扣（LeetCode），是通过层序遍历实现的，这里贴一下我的反序列化代码，也就是输入一个字符串，得到一棵树，其中利用了string流进行字符串切割，每次读入两个(左右孩子)，而主体逻辑和层序遍历相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
TreeNode* deserialize(string data) {
    if(data=="")
        return NULL;
    stringstream in(data);
    string v,v1,v2;
    queue<TreeNode*> q;
    TreeNode* root=new TreeNode;
    in>>v;
    root->val=stoi(v);
    q.push(root);
    while(!q.empty())
    {
        int cnt=q.size();
        for(int i=1;i<=cnt&&in>>v1&&in>>v2;++i)
        {
            TreeNode* node=q.front();
            q.pop();
            if(v1!="null")
            {
                TreeNode* node1=new TreeNode;
                node1->val=stoi(v1);
                node->left=node1;
                q.push(node1);
            }
            if(v2!="null")
            {
                TreeNode* node2=new TreeNode;
                node2->val=stoi(v2);
                node->right=node2;
                q.push(node2);
            }
        }
    }
    return root;
}

井号法(深度优先遍历序列)

井号法是把包括叶节点的每个节点都视为有两个孩子，为空则填#，然后进行深度优先遍历后得到的序列(一般是先序遍历)，故而也会通过深度优先遍历来恢复。比如最上面那张图的二叉树，#法表示为：ABD##FK##I##CEH##J##G##。

恢复代码为：

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode *createTree()
{
    char c;
    scanf("%c", &c);
    if (c == '#') //如果遇到#，返回空
        return NULL;
    TreeNode *node = new TreeNode;
    node->val = c;
    node->left = createTree();
    node->right = createTree();
    return node;
}

由于深度优先遍历的递归版本代码量本来就小，所以这种方法建树的代码也要少一点。不过，实际上这两种方法都是用特殊字符代替空值来体现二叉树的层次的。

(先序/后序)&中序遍历序列

这也是考察最多的问题了，通过先序、后序遍历序列中的一个，以及中序遍历序列，就可以唯一确定一棵树。具体可见105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）基本思路是：先序遍历的第一个值就是根节点，而中序遍历中可以依此分隔左右子树，然后再根据大小在先序遍历序列中找到左右子树分点，递归求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> preOrderTrav,inOrderTrav;
TreeNode *createTree(int pbeg, int pend, int ibeg, int iend)
{
    if (pbeg == pend)
        return NULL;
    TreeNode *node = new TreeNode;
    node->val = preOrderTrav[pbeg];
    int pos =find(inOrderTrav.begin()+ibeg,inOrderTrav.end(),node->val)-inOrderTrav.begin(),
        mid = pbeg + pos - ibeg + 1; //在中序遍历序列中找到当前的根节点，并依此计算先序遍历中的分点
    node->left = createTree(pbeg + 1, mid, ibeg, pos);
    node->right = createTree(mid, pend, pos + 1, iend);
    return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    preOrderTrav=preorder,inOrderTrav=inorder;
    return createTree(0,preorder.size(),0,inorder.size());
}

随便写几个问题，就这么多了，树结构可写的真是太多了，有时间再来补吧……