【C++进阶】二叉树进阶-蒲公英云

?C++学习历程：入门

博客主页：一起去看日落吗
持续分享博主的C++学习历程
博主的能力有限，出现错误希望大家不吝赐教
分享给大家一句我很喜欢的话： 也许你现在做的事情，暂时看不到成果，但不要忘记，树?成长之前也要扎根，也要在漫长的时光?中沉淀养分。静下来想一想，哪有这么多的天赋异禀，那些让你羡慕的优秀的人也都曾默默地翻山越岭?。

✨ ⭐️ ? ?

? 1. 二叉搜索树
- ? 1.1 二叉搜索树概念
- ? 1.2 二叉搜索树操作
- - ⭐️ 1.2.1 查找
  - ⭐️ 1.2.2 插入
  - ⭐️ 1.2.3 删除
- ? 1.3 二叉搜索树的实现
- - ⭐️ 1.3.1 BinarySearchTree.hpp
  - ⭐️ 1.3.2 main.cpp
- ? 1.4 二叉搜索树的应用
- - ⭐️ 1.4.1 _BinarySearchTree.hpp
  - ⭐️ 1.4.2 main.cpp
- ? 1.5 二叉搜索树的性能分析
? 2. 二叉树OJ题
- ✨ 第一题
- ✨ 第二题
- ✨ 第三题
- ✨ 第四题
- ✨ 第五题
- ✨ 第六题
- ✨ 第七题
- ✨ 第八题
- ✨ 第九题
- ✨ 第十题

? 1. 二叉搜索树

? 1.1 二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

在这里插入图片描述

? 1.2 二叉搜索树操作

⭐️ 1.2.1 查找

请添加图片描述

若根节点不为空：

如果 (根节点 key == 查找 key)，返回 true；

如果 (根节点 key > 查找 key)，在其左子树查找；

如果 (根节点 key < 查找 key)，在其右子树查找；

否则，返回 false；

二叉搜索树结构查找一个值最多查找高度次。

⭐️ 1.2.2 插入

插入的具体过程如下：

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点

在这里插入图片描述

⭐️ 1.2.3 删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：

a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：

情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除

在这里插入图片描述

? 1.3 二叉搜索树的实现

⭐️ 1.3.1 BinarySearchTree.hpp

#pragma once
#include<iostream>
using namespace std;
namespace KEY
{
    template<class K>
    struct BSTreeNode
    {
        BSTreeNode<K>* _left;
        BSTreeNode<K>* _right;
        K _key;
        BSTreeNode(const K& key)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
        {
    }
    };
    template<class K>
    class BSTree
    {
        typedef BSTreeNode<K> Node;
    public:
        bool Insert(const K& key)
        {
            //空树,直接插入
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            //查找要插入的位置
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)//往右子树查找
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)//往左子树查找
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;//默认不支持冗余    
                }
            }
            //new节点,这里需要在BSTreeNode补构造函数
            cur = new Node(key);
            if (parent->_key < cur->_key)//新节点链接到父的左还是右,还需要再比一次
            {
                parent->_right = cur;//关联
            }
            else
            {
                parent->_left = cur;//关联
            }
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //删除
                    if (cur->_left == nullptr)//ab
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_right;//右作根
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)//ac
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else//d
                    {
                        //找右树的最小节点去替代删除
                        Node* minRightParent = cur;
                        //cur->right一定不为空
                        Node* minRight = cur->_right;
                        //最小节点
                        while (minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //替代
                        cur->_key = minRight->_key;
                        //minRight的左一定为空,但右不一定为空,minRightParent->_left不一定是minRight
                        if (minRight == minRightParent->_left)//删除5,找6
                        {
                            minRightParent->_left = minRight->_right;
                        }
                        else//删除7,找8
                        {
                            minRightParent->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
        bool InsertR(const K& key)
        {
            return _InsertR(_root, key);
        }
        Node* FindR(const K& key)
        {
            return _FindR(_root, key);
        }
        bool EraseR(const K& key)
        {
            return _EraseR(_root, key);
        }
        //BSTree() = default;//C++11
        BSTree()
            : _root(nullptr)
        {
    }
        ~BSTree()
        {
            _Destroy(_root);
        }
        //BSTree(const BSTree& t)
        BSTree(const BSTree<K>& t)
        {
            _root = _Copy(t._root);
        }
        //BSTree& operator=(BSTree t)
        BSTree<K>& operator=(BSTree<K> t)//现代写法 t1 = t2
        {
            std::swap(_root, t._root);
            return *this;
        }
    private:
        Node* _Copy(Node* root)
        {
            if (root == nullptr)
            {
                return nullptr;
            }
            //深拷贝根
            Node* newRoot = new Node(root->_key);
            //递归拷贝左右子树
            newRoot->_left = _Copy(root->_left);
            newRoot->_right = _Copy(root->_right);
            //返回根
            return newRoot;
        }
        void _Destroy(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            //后序
            _Destroy(root->_left);
            _Destroy(root->_right);
            delete root;
        }
        bool _EraseR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                return false;
            }
            else if (root->_key < key)
            {
                return _EraseR(root->_right, key);
            }
            else if (root->_left > key)
            {
                return _EraseR(root->_left, key);
            }
            else
            {
                //删除
                Node* del = root;
                if (root->_left == nullptr)//ab
                {
                    root = root->_right;
                }
                else if (root->_right == nullptr)//ac
                {
                    root = root->_left;
                }
                else//d
                {
                    //替代
                    Node* minRight = root->_right;
                    while (minRight->_left)
                    {
                        minRight = minRight->_left;
                    }
                    root->_key = minRight->_key;
                    //大事化小,小事化了
                    return _EraseR(root->_right, minRight->_key);
                }
                delete del;
                return true;
            }
        }
        Node* _FindR(Node* root, const K& key)
        {
            if (root == nullptr)
            {
                return nullptr;
            }
            if (root->_key < key)
            {
                return _FindR(root->_right, key);
            }
            else if (root->_key > key)
            {
                return _FindR(root->_left, key);
            }
            else
            {
                return root;
            }
        }
        bool _InsertR(Node*& root, const K& key)
        {
            if (root == nullptr)
            {
                root = new Node(key);
                return true;
            }
            else
            {
                if (root->_key < key)
                {
                    return _InsertR(root->_right, key);
                }
                else if (root->_key > key)
                {
                    return _InsertR(root->_left, key);
                }
                else
                {
                    return false;
                }
            }
        }
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}

⭐️ 1.3.2 main.cpp

#include "BinarySearchTree.hpp"
void TestBSTree1()
{
    int a[] = {
     5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    KEY::BSTree<int> t;
    for (auto e : a)
    {
        t.Insert(e);
    }
    t.InOrder();
    t.Erase(7);
    t.InOrder();
    t.Erase(5);
    t.InOrder();
}
void TestBSTree2()
{
    int a[] = {
     5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    KEY::BSTree<int> t;
    for (auto e : a)
    {
        t.Insert(e);
    }
    t.InOrder();
    //挨个删除
    for (auto e : a)
    {
        t.Erase(e);
        t.InOrder();
    }
    //先删除左树,再删除根
    /*t.Erase(0);
    t.Erase(1);
    t.Erase(2);
    t.Erase(3);
    t.Erase(4);
    t.Erase(5);
    t.InOrder();*/
}
void TestBSTree3()
{
    int a[] = {
     5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    KEY::BSTree<int> t;
    for (auto e : a)
    {
        t.InsertR(e);
    }
    t.InOrder();
    //挨个删除
    for (auto e : a)
    {
        t.Erase(e);
        t.InOrder();
    }
    //先删除左树,再删除根
    /*t.Erase(0);
    t.Erase(1);
    t.Erase(2);
    t.Erase(3);
    t.Erase(4);
    t.Erase(5);
    t.InOrder();*/
}
void TestBSTree4()
{
    int a[] = {
     5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
    KEY::BSTree<int> t;
    for (auto e : a)
    {
        t.Insert(e);
    }
    t.InOrder();
    KEY::BSTree<int> copy = t;
    copy.InOrder();
    KEY::BSTree<int> assign;
    assign = t;
    assign.InOrder();
}
int main()
{
    TestBSTree1();
    cout << "-------------------" << endl;
    TestBSTree2();
    cout << "-------------------" << endl;
    TestBSTree3();
    cout << "-------------------" << endl;
    TestBSTree4();
    return 0;
}

请添加图片描述

? 1.4 二叉搜索树的应用

K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。

⭐️ 1.4.1 _BinarySearchTree.hpp

#pragma once
#include<iostream>
#include<string>
using namespace std;
namespace KEY
{
    //...
}
namespace KEY_VALUE
{
    template<class K, class V>
    struct BSTreeNode
    {
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
        K _key;
        V _value;
        BSTreeNode(const K& key, const V& value)
            : _left(nullptr)
            , _right(nullptr)
            , _key(key)
            , _value(value)
        {
    }
    };
    template<class K, class V>
    class BSTree
    {
        typedef BSTreeNode<K, V> Node;
    public:
        bool Insert(const K& key, const V& value)
        {
            //空树,直接插入
            if (_root == nullptr)
            {
                _root = new Node(key, value);
                return true;
            }
            //查找要插入的位置
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)//往右子树查找
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)//往左子树查找
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;//默认不支持冗余
                }
            }
            //new节点,这里需要在BSTreeNode补构造函数
            cur = new Node(key, value);
            if (parent->_key < cur->_key)//新节点链接到父的左还是右,还需要再比一次
            {
                parent->_right = cur;//关联
            }
            else
            {
                parent->_left = cur;//关联
            }
            return true;
        }
        Node* Find(const K& key)
        {
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }
        bool Erase(const K& key)
        {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    //删除
                    if (cur->_left == nullptr)//ab
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_right;//右作根
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_right;
                            }
                            else
                            {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)//ac
                    {
                        //没有父亲
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            //确定目标位置父亲的左还是右和目标位置的孩子关联(目标位置的左右孩子在外层if已经确定了)
                            if (cur == parent->_left)
                            {
                                parent->_left = cur->_left;
                            }
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    else//d
                    {
                        //找右树的最小节点去替代删除
                        Node* minRightParent = cur;
                        //cur->right一定不为空
                        Node* minRight = cur->_right;
                        //最小节点
                        while (minRight->_left)
                        {
                            minRightParent = minRight;
                            minRight = minRight->_left;
                        }
                        //替代
                        cur->_key = minRight->_key;
                        //minRight的左一定为空,但右不一定为空,minRightParent->_left不一定是minRight
                        if (minRight == minRightParent->_left)//删除5,找6
                        {
                            minRightParent->_left = minRight->_right;
                        }
                        else//删除7,找8
                        {
                            minRightParent->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    private:
        void _InOrder(Node* root)
        {
            if (root == nullptr)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }
    private:
        Node* _root = nullptr;
    };
}

⭐️ 1.4.2 main.cpp

#include"_BinarySearchTree.hpp"
void TestBSTree1()
{
    KEY_VALUE::BSTree<string, string> dict;
    dict.Insert("sort", "排序");
    dict.Insert("insert", "插入");
    dict.Insert("tree", "树");
    dict.Insert("left", "左边");
    dict.Insert("right", "右边");
    //...
    string str;
    while(cin >> str)
    {
        if(str == "Q")
        {
            break;
        }
        else
        {
            auto ret = dict.Find(str);
            if(ret == nullptr)
            {
                cout << "拼写错误,请检查你的单词" << endl;
            }
            else
            {
                cout << ret->_key <<  "->" << ret->_value << endl;
            }
        }
    }
}
void TestBSTree2()
{
    string str[] = {
    "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
    KEY_VALUE::BSTree<string, int> countTree;
    for(auto& e : str)
    {
        auto ret = countTree.Find(e);
        if(ret == nullptr)
        {
            countTree.Insert(e, 1);//第一次出现
        }
        else
        {
            ret->_value++;//非第一次出现
        }
    }
    countTree.InOrder();
}
int main()
{
    TestBSTree1();
    TestBSTree2();
    return 0;
}

请添加图片描述

? 1.5 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

在这里插入图片描述

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)
最差情况下，二叉搜索树退化为单支树(或者类似单支)

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们学习的AVL树和红黑树就可以上场了。

? 2. 二叉树OJ题

✨ 第一题

链接：根据二叉树创建字符串

在这里插入图片描述
请添加图片描述

解题思路

我们可以使用递归的方法得到二叉树的前序遍历，并在递归时加上额外的括号。

会有以下 4 种情况：

如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；

请添加图片描述
如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；

请添加图片描述

如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 ‘()’\text{`()’}‘()’ 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。

请添加图片描述

代码演示

class Solution {
public:
    string tree2str(TreeNode* root) {
        if(root == nullptr)
            return "";
        if(root -> left == nullptr && root -> right == nullptr)
            return to_string(root -> val);
        if(root -> right == nullptr)
            return to_string(root -> val) + '(' + tree2str(root -> left) + ')';
        return to_string(root -> val) + '(' + tree2str(root -> left) + ')' + '(' + tree2str(root -> right) + ')';
    }
};

✨ 第二题

链接：二叉树的层序遍历1

在这里插入图片描述

解题思路

按层打印：题目要求的二叉树的从上至下打印（即按层打印），又称为二叉树的广度优先搜索（BFS）。BFS 通常借助队列的先入先出特性来实现。 II. 每层打印到一行：将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

算法流程

特例处理：当根节点为空，则返回空列表 [] ；
初始化：打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；
BFS 循环：当队列 queue 为空时跳出；
大小：计算队列的大小也就是当前根结点有多少孩子结点；
新建一个临时列表 tmp ，用于存储当前层打印结果；
当前层打印循环：循环次数为当前层节点数（即队列 queue 长度）；
出队：队首元素出队，记为 node；
打印：将 node.val 添加至 tmp 尾部；
添加子节点：若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
将当前层结果 tmp 添加入 res 。
返回值：返回打印结果列表 res 即可。

代码演示：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root != nullptr)
            q.push(root);
        //开始遍历
        while(!q.empty())
        {
            int size = q.size();
            vector<int> vec;
            for(int i = 0;i < size;i++)
            {
                TreeNode* node = q.front();//第一个节点
                q.pop();
                vec.push_back(node -> val);
                if(node -> left != nullptr)
                    q.push(node -> left);
                if(node -> right != nullptr)
                    q.push(node -> right);
            }
            //保存数据
            res.push_back(vec);
        }
        return res;
    }
};

✨ 第三题

链接：二叉树的层序遍历2

请添加图片描述

解题思路

很简单，正着遍历一遍然后reveres反过来就可以了

代码演示

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if(root != nullptr)
            q.push(root);
        //开始遍历
        while(!q.empty())
        {
            int size = q.size();
            vector<int> vec;
            for(int i = 0;i < size;i++)
            {
                TreeNode* node = q.front();//第一个节点
                q.pop();
                vec.push_back(node -> val);
                if(node -> left != nullptr)
                    q.push(node -> left);
                if(node -> right != nullptr)
                    q.push(node -> right);
            }
            //保存数据
            res.push_back(vec);
        }
        reverse(res.begin(),res.end());//反转
        return res;
    }
};

✨ 第四题

链接：二叉树最近的公共祖先

请添加图片描述

解题思路

根据定义，若 rootrootroot 是 p,qp, qp,q 的最近公共祖先，则只可能为以下情况之一：

p 和 q 在 roott 的子树中，且分列 root 的异侧（即分别在左、右子树中）；
p=root ，且 q 在 root 的左或右子树中；
q=root ，且 p 在 root 的左或右子树中；

代码演示

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q)
            return root;
        TreeNode *left = lowestCommonAncestor(root -> left ,p ,q);
        TreeNode *right = lowestCommonAncestor(root -> right ,p ,q);
        if(left == nullptr)
            return right;
        if(right == nullptr)
            return left;
        return root;
    }
};

✨ 第五题

链接：二叉搜索树和双向链表

请添加图片描述

解题思路

二叉搜索树最左端的元素一定最小，最右端的元素一定最大，符合“左中右”的特性，因此二叉搜索树的中序遍历就是一个递增序列，我们只要对它中序遍历就可以组装称为递增双向链表。

代码演示

class Solution {
public:
    TreeNode* head = nullptr;
    TreeNode* prev = nullptr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == nullptr)
            return nullptr;
        Convert(pRootOfTree -> left);
        if(prev == nullptr)
        {
            head = pRootOfTree;
            prev = pRootOfTree;
        }
        else
        {
            prev -> right = pRootOfTree;
            pRootOfTree -> left = prev;
            prev = pRootOfTree;
        }
        Convert(pRootOfTree -> right);
        return head;
    }
};

✨ 第六题

链接：从前序与中序遍历序列构造二叉树

请添加图片描述

解题思路：

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

代码演示：

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 若节点个数等于0
        if(preorder.size() == 0){
            return nullptr;
        }
        // 先序遍历的第一个节点 preorder[0] 为 根节点 root
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> s;
        // 将根节点入栈
        s.push(root);
        // 初始化扫描中序遍历的指针
        int idx = 0;
        for(int i = 1; i < preorder.size(); i++){
            TreeNode* node = s.top();
            // 若 栈顶元素的值 与 中序遍历当前所指的值 不相同
            // 表明当前节点存在子树
            if(node->val != inorder[idx]){
                node->left = new TreeNode(preorder[i]);
                s.push(node->left);
            }
            // 若 栈顶元素的值 与 中序遍历当前所指的值 相同
            // 表明当前节点不存在子树，即为最左下角的节点
            else{
                // 当 栈非空 且 栈顶元素的值 与 中序遍历当前所指的值 相同
                while(!s.empty() && s.top()->val == inorder[idx]){
                    // 指针向右扫描中序遍历
                    node = s.top();
                    // 弹出栈中所有与当前指针所指元素值相同的节点
                    s.pop();
                    // 中序遍历指针向右移动
                    idx++;
                }
                // while循环结束后，当前node所指向的节点就是需要重建右子树的节点
                node->right = new TreeNode(preorder[i]);
                s.push(node->right);
            }
        }
        return root;
    }
};

✨ 第七题

链接：从中序与后序遍历构造二叉树

请添加图片描述

解题思路

首先解决这道题我们需要明确给定一棵二叉树，我们是如何对其进行中序遍历与后序遍历的：

中序遍历的顺序是每次遍历左孩子，再遍历根节点，最后遍历右孩子。
后序遍历的顺序是每次遍历左孩子，再遍历右孩子，最后遍历根节点。

代码演示

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }
        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];
        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;
        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

✨ 第八题

链接：二叉树的前序遍历

请添加图片描述

解题思路：

首先我们需要了解什么是二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，我们只要首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

代码演示：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == nullptr)
            return res;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while(!stk.empty() || node != nullptr)
        {
            while(node != nullptr)
            {
                res.push_back(node -> val);
                stk.push(node);
                node = node -> left;
            }
            node = stk.top();
            stk.pop();
            node = node -> right;
        }
        return res;
    }
};

✨ 第九题

链接：二叉树的中序遍历

请添加图片描述

解题思路

和前序遍历思路差不多

代码演示

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

✨ 第十题

链接：二叉树的后续遍历

请添加图片描述

解题思路

我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。

代码演示

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode *> stk;
        TreeNode *prev = nullptr;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val);
                prev = root;
                root = nullptr;
            } else {
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};