二叉树的常见算法

不念不忘少年蓝@ 2022-04-22 11:20 231阅读 0赞

1.二叉树的遍历算法  
二叉树的遍历主要分为三种：先序遍历，中序遍历和后序遍历。还有一种就是按照层次遍历。  
按照惯例，左孩子优先于右孩子，那么：

先序遍历指的就是先访问本节点，再访问该节点的左孩子和右孩子；  
中序遍历指的就是：先访问左孩子，再访问本节点，最后访问右孩子；  
后序遍历指的就是：先访问左右孩子，最后访问本节点。  
层次遍历：按照树的每一层(高度)进行遍历。  
树的节点的数据结构常声明为：  
![20181104180808581.png][]

约定给出根节点，分别使用三种遍历方式得到二叉树的序列：得益于递归的简洁性，三种遍历方式的递归算法也是非常简洁和易懂的。

### (1). 先序遍历 ###

![20181104180836858.png][]

先序遍历的理解：沿着最左侧通路自顶而下访问各个节点，自底而上遍历对应的右子树。迭代版本需要用到栈这种数据结构。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70][]  
(2). 中序遍历

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 2][]

后序遍历的迭代版本和前序遍历类似：  
可以证明，右孩子优先的先序遍历序列的逆序列就是左孩子优先的后序遍历序列。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 3][]

假设根节点的值为a，L1和R1分别是左子树和右子树在右孩子优先的先序遍历序列，L2和R2分别是左子树和右子树在左孩子优先的后序遍历序列，所以只需要证明:序列"a,R1,L1"是序列"L2,R2,a"的逆序列即可。  
从序列的组成来看，只需要证明R1是R2的逆序列且L1是L2的逆序列，显然这就将问题分解，平凡的情况下是显然成立的，因此可以归纳证明出这个结论。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 5][]

## 2. 二叉树的其它算法 ##

### (1). 二叉树的深度 ###

递归版本非常简洁，也非常易懂；迭代版本则需要利用我们之前介绍的按照层次遍历，层数就是二叉树的深度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 6][]

### (2). 二叉树的镜像 ###

操作给定的二叉树，将其变换为源二叉树的镜像。使用递归，当节点存在至少一个孩子时，交换左右孩子，再递归处理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 7][]

(3). 平衡二叉树  
输入一棵二叉树，判断该二叉树是否是平衡二叉树。  
平衡二叉树指的是：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，见百度百科。关键点：子树的高度差不超过1且子树也是平衡树。构造一个递归函数IsBalanced来判断这两个条件。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 8][]

### (4). 对称的二叉树 ###

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 9][]

### (5). 把二叉树打印成多行 ###

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。  
在求二叉树的深度的时候，迭代解法起始我们已经做了这个事情，只是没有按照多行输出，所以只需要记录每一行的`val`即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 10][]

### (6). 二叉树的下一个结点 ###

给定一个二叉树和其中的一个结点，请找出**中序遍历**顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。  
节点的数据结构表示为：

![20181104181351572.png][]

若允许一定的空间复杂度，可以直接中序遍历保存序列之后直接查找。这种方法就不介绍了，下面介绍常数空间的算法：

如果该节点有右孩子，必然下一个节点就是该节点的右孩子的沿着左侧链下的最后一个左孩子；  
该节点没有右孩子，也没有父节点，说明这个节点是最后一个节点；  
该节点没有右孩子，但是有父节点且是父节点的左孩子，必然下一个节点就是该节点的父节点；  
该节点没有右孩子，且有父节点且是父节点的右孩子，要么该节点是最后一个节点，要么沿着父链上升，之后第一个节点的是其父节点的左孩子，这个父节点就是下一个节点。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 11][]

(7). 二叉搜索树与双向链表  
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。  
二叉搜索树(Binary Search Tree, BST)：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。详见百度百科。  
中序遍历一颗二叉搜索树，必然得到的是一个有序的序列。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 12][]

### (8). 二叉树中和为某一值的路径 ###

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 13][]

(9). 按之字形顺序打印二叉树  
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。  
思路，构建两个栈，依次保存奇数行和偶数行的节点，注意左右孩子的入栈顺序；例如：从第0行到第1行，第1行先左孩子，再右孩子入栈，这样出栈的时候才会从右往左的顺序；从第1行到第2行，先右孩子，再左孩子入栈，这样才能保证出栈的顺序是从左往右。  
//按之字形顺序打印二叉树  
vector<vector<int>> Print(TreeNode \*pRoot) \{  
    if (!pRoot) return \{\};  
    vector<vector<int>> result;  
    stack<TreeNode \*> odd, even;  
    even.push(pRoot);        //从第零行开始  
    while (!even.empty() || !odd.empty()) \{  
        vector<int> line;  
        if (odd.empty()) \{  
            while (!even.empty()) \{  
                TreeNode \*curr\_node = even.top();  
                even.pop();  
                line.push\_back(curr\_node->val);  
                if (curr\_node->left) odd.push(curr\_node->left);  
                if (curr\_node->right) odd.push(curr\_node->right);    //注意，先左后右  
            \}  
        \}  
        else \{  
            while (!odd.empty()) \{  
                TreeNode \*curr\_node = odd.top();  
                odd.pop();  
                line.push\_back(curr\_node->val);  
                if (curr\_node->right) even.push(curr\_node->right);  
                if (curr\_node->left) even.push(curr\_node->left);        //注意，先右后左  
            \}              
        \}  
        result.push\_back(line);  
    \}  
    return result;

### 10. 二叉搜索树的第k个结点 ###

给定一棵二叉搜索树，请找出其中的第k小的结点。例如： `（5，3，7，2，4，6，8）` 中，按结点数值大小顺序第三小结点的值为4。 如果按照中序遍历存储起来，这种思路是非常简单且容易实现的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 14][]

11. 二叉搜索树的后序遍历序列  
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。  
对于后序遍历，我们知道序列最后一个数字必定是二叉搜索树的根节点，由于保证序列的任意两个数字都互不相同，设序列中第一个大于根节点的位置为k，那么\[0,k)这一段子序列必然是左子树后序遍历得到的子序列，\[k+1, end)必然是右子树后序遍历得到的子序列，依此递归即可，另外，在\[k+1, end)若存在有一个节点的值小于根节点，说明不是二叉搜索树的后序遍历序列 。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 15][]

### 11. 重建二叉树 ###

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列`{1,2,4,7,3,5,6,8}`和中序遍历序列`{4,7,2,1,5,3,8,6}`，则重建二叉树并返回。

//重建二叉树  
TreeNode \*reConstructBinaryTree(vector<int>::iterator pre\_first,   
                            vector<int>::iterator pre\_last,  
                                vector<int>::iterator vin\_first,  
                                vector<int>::iterator vin\_last) \{  
    if (vin\_last - vin\_first != pre\_last - pre\_first ||  
            pre\_last == pre\_first ||  
            vin\_first == vin\_last) \{  
        return nullptr;  
    \}  
    TreeNode \*curr\_node = new TreeNode(\*pre\_first);  
    if (pre\_last == pre\_first + 1) return curr\_node;  
    auto iter = vin\_first;  
    while (iter < vin\_last) \{  
        if (\*iter == \*pre\_first) break;  
        iter++;  
    \}  
    int len = iter - vin\_first;  
    curr\_node->left = reConstructBinaryTree(pre\_first + 1, pre\_first + len + 1, vin\_first, iter);  
    curr\_node->right = reConstructBinaryTree(pre\_first + len + 1, pre\_last, iter + 1, vin\_last);  
    return curr\_node;  
\}  
TreeNode \*reConstructBinaryTree(vector<int> pre, vector<int> vin) \{  
  return reConstructBinaryTree(pre.begin(), pre.end(), vin.begin(), vin.end());  
\}

### 12. 树的子结构 ###

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 16][]

[20181104180808581.png]: /images/20220422/2073eb3d3f024b52a7a5d676be6de150.png
[20181104180836858.png]: /images/20220422/9eeebe39497d4d588eaf79592e38bb5f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70]: /images/20220422/8b9e40dd3ec041b2952e107c9ab8774c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 1]: /images/20220422/b245ec157e064d1fa33cef28f1b6680c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 2]: /images/20220422/b5e9a26cdf6e4efb8638f7afca0c4883.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 3]: /images/20220422/2e7cee10d5764fd9a3c6c8dae0b3aad6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 4]: /images/20220422/c4358676262a43448a9b08324dd9fd13.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 5]: /images/20220422/e85fc135a08d4c54af4b9a20c136157a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 6]: /images/20220422/241d632abed0470b99a29d857c1dafc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 7]: /images/20220422/cc476b3edf044b518f3b6eeb28c1e668.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 8]: /images/20220422/dc165b1791474f80bd8448575a91e710.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 9]: /images/20220422/631502989afb4606ae9f5f46c8c5d8cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 10]: /images/20220422/2c0a7ae9374345478d057a533a46ba47.png
[20181104181351572.png]: /images/20220422/e15365e32de646c494ca8ef2f81e43d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 11]: /images/20220422/650c88ade8094e9d9c03db1bc5358209.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 12]: /images/20220422/30eee357b2e944e6b46db30ce8f27f05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 13]: /images/20220422/5f43e5262dbf49f8a9f675df26803dfb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 14]: /images/20220422/85ea547d18c6461aa42b040ca42b119d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 15]: /images/20220422/ffe62ead88d944b2b0bcc5968eabf995.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjE3NTU3MA_size_16_color_FFFFFF_t_70 16]: /images/20220422/4ee162bbfcf341fb9ec1f9f8a26137d6.png