【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

不会自动生成，还是我自己写目录吧 -.-

文章目录

前言
一、稍微简单一点的二叉树OJ题
二、相对困难一点的二叉树OJ题
总结

前言

在看这篇文章前希望大家是学过二叉树的，不然理解起来可能会比较费劲，但我会尽自己的努力让大家学会这些题（都是往年大厂必考题哦~）,本次一共包含了12道二叉树的OJ题，力扣与牛客网都有，大家要做的话直接点我发的链接即可。

一、稍微简单一点的二叉树OJ题

第一题：根据二叉树创建字符串

力扣链接：力扣

要求：

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

从题目要求我们可以了解到，此题分为三种情况：1.当左子树不为空，右子树为空。这个时候左子树的括号不能省略，右子树的括号可以省略 2.当左子树为空，右子树为空。这个时候为了不破坏输入与输出一一映射的关系，所以不能省略左子树的括号，参考第二个例子。3.左子树为空，右子树也为空，括号都可以省略。下面我们照着这个思路编写代码：

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

首先我们可以看到函数的返回值是个字符串，所以如果递归的这个节点为空，那么我们要返回一个不影响结果的字符串，所以我们返回空串。然后定义一个字符串对象，一旦走到这里说明root肯定不为空，那么我们就在字符串中把节点的val加上，在这里用整形转字符串函数将val转为字符串。然后就到判断条件了，经过我们刚刚的分析，当左子树不为空我们要加括号，当左子树为空右子树不为空我们也要给左子树加上括号（为了不破坏关系），所以当左树不为空或者左树为空右树不为空我们就加上括号，左树右树都为空就不进入循环了所以肯定没有括号，我们先加左括号然后递归这棵树的左子树，直到左子树都递归完才加上右括号，即使左子树为空右子树不为空的时候，也会先加左括号然后递归一个空字符串在加上右括号。然后我们在判断右子树，如果右子树不为空就加上括号同理要递归右子树。然后我们返回结果即可。递归图如下：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

第二题：二叉树的层序遍历

力扣链接：力扣

题目要求：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

层序遍历大家应该不会陌生，由于返回的是一个二维数组所以我们需要每次遍历完一层把这一层的节点放到向量中，所以需要两个栈配合才能完成遍历，下面我们直接上代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
         vector<vector<int>> vv;
         if (root==nullptr)
         {
             return vv;
         }
         stack<TreeNode*> st;
         stack<TreeNode*> st2;
         st.push(root);
         while (!st.empty())
         {
             int sz = st.size();
             vector<int> v;
             for (int i = 0;i<sz;i++)
             {
                 TreeNode* tmp = st.top();
                 st.pop();
                 v.push_back(tmp->val);
                 if (tmp->left)
                 {
                     st2.push(tmp->left);
                 }
                 if (tmp->right)
                 {
                     st2.push(tmp->right);
                 }
             }
             vv.push_back(v);
             while (!st2.empty())
             {
                 st.push(st2.top());
                 st2.pop();
             }
             v.clear();
         }
         return vv;
    }
};

首先判断根节点是否为空，如果为空我们就返回一个二维数组。然后用两个栈，一个是当前层，一个保留下一层，首先先入根节点，进入循环后我们一定要记录栈的大小，然后用一个一维数组保存每一层的值，我们用一个循环来确定树中当前层的个数，每次出栈时都需要判断栈顶元素是否有左右子树，如果有就保存到另一个栈中供下次使用，当循环结束后就将一层的数据尾插到二维数组中，这个时候我们就该将保存的下一层的节点放到用于遍历的栈中，最后可以将一维数组清空也可以不清空，因为每次进入循环都会重新开一个一维数组，整体大循环的条件就是看用于遍历的那个栈是否为空，下面我们画一个示意图：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

第三题：二叉树的层序遍历II

力扣链接：力扣

题目要求：

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

看到这道题不知道大家有没有什么想法呢？这不就是把我们刚刚层序遍历的那个二维数组逆置了一下吗，我们直接上代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
         vector<vector<int>> vv;
         if (root==nullptr)
         {
             return vv;
         }
         stack<TreeNode*> st;
         st.push(root);
         //queue<TreeNode*> q;
         stack<TreeNode*> st2;
         while (!st.empty())
         {
             int sz = st.size();
             vector<int> v;
             //在遍历栈的时候要注意，在循环出栈的时候会影响循环的次数，所以应该先
             //提前保存栈的size，循环用保存的这个变量
             for (int i = 0;i<sz;i++)
             {
                 TreeNode* tmp = st.top();
                 st.pop();
                 v.push_back(tmp->val);
                 if (tmp->left)
                 {
                     st2.push(tmp->left);
                 }
                 if (tmp->right)
                 {
                     st2.push(tmp->right);
                 }
             }
             vv.push_back(v);
             while (!st2.empty())
             {
                 st.push(st2.top());
                 st2.pop();
             }
             v.clear();
         }
         reverse(vv.begin(),vv.end());
         return vv;
    }
};

没错！我们直接将这个二维数组逆置就是这道题的答案。

第四题：二叉树的最近公共祖先

力扣：力扣

题目要求：百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

此题有三种情况，第一种情况是当p在root的左边，q在root的右边，这种情况下root一定为公共祖先。第二种情况是：p和q都在root的左边，这种情况下需要去root的左子树递归寻找公共祖先。第三种情况是：p和q都在root的右边，这种情况下需要去root的右子树递归寻找公共祖先。

下面我们实现代码：

class Solution {
public:
    bool isExist(TreeNode* root,TreeNode* pq)
    {
        if (root==nullptr)
        {
            return false;
        }
        if (root==pq)
        {
            return true;
        }
        return isExist(root->left,pq)||isExist(root->right,pq);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (root==nullptr)
       {
           return nullptr;
       }
       if (p==root||q==root)
       {
           return root;
       }
       bool pInleft = isExist(root->left,p);
       bool pInright = !pInleft;
       bool qInleft = isExist(root->left,q);
       bool qInright = !pInleft;
       if ((pInleft&&qInright)||(pInright&&qInleft))
       {
           return root;
       }
       if (pInleft&&qInleft)
       {
           return lowestCommonAncestor(root->left,p,q);
       }
       if (pInright&&qInright)
       {
           return lowestCommonAncestor(root->right,p,q);
       }
       return root;
    }
};

首先判断根节点是否为空，如果根节点都为空了那就没有找的必要了直接返回nullptr即可。然后我们发现，只要p或q之间有一个是根节点，那么公共祖先一定是根节点。然后我们判断p在root的左边还是右边，同样判断q，当p在root的左边q再root的右边或者p在root的右边，q在root的左边，这种时候root一定为公共祖先，然后当两棵树都在同一个方向时就去子树递归查找公共祖先即可。判断节点是否在一个树中的函数很简单，当root在递归的时候都为空还没找到要查找的节点这就说明这个节点不在这棵树中，当root不为空要不就是找到了要不就是去当前节点的左子树或者右子树继续查找，只要找到了就返回true。

第五题：二叉搜索树与双向链表

牛客网链接：二叉搜索树与双向链表_牛客题霸_牛客网

题目要求：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

这道题有很多种解法，但是由于题目要求只能调整树中节点的指向所以解题方法少了很多，最简单的方法就是在中序遍历的时候修改节点的指向，但是由于每次递归的时候只能修改当前节点的前驱节点，因为这个时候还没有递归到下一个节点所以无法链接下一个节点，虽然在当前节点不能修改下一个节点的后继，但是在递归到下一个节点的时候我们就可以用前驱节点的后继指针指向这个节点，所以我们需要加入一个指针指向每次递归的前一个节点，并且这个节点的传参方式必须是引用传参，只有引用传参才能在每次递归的时候将上一次的指向修改。下面我们直接写代码：

class Solution {
public:
    void _Convert(TreeNode* root,TreeNode*& pre)
	{
		if (root==nullptr)
		{
			return ;
		}
		_Convert(root->left,pre);
		root->left = pre;
		if (pre)
		{
			pre->right = root;
		}
		pre = root;
		_Convert(root->right,pre);
	}
    TreeNode* Convert(TreeNode* pRootOfTree) {
		if (pRootOfTree==nullptr)
		{
			return nullptr;
		}
		TreeNode* head = pRootOfTree;
		while (head->left)
		{
			head = head->left;
		}
		TreeNode* pre = nullptr;
		_Convert(pRootOfTree,pre);
		return head;
    }
};

首先判断根节点是否为空，如果为空则返回空指针。然后我们用一个指针来遍历这个数的左子树直到走到最左边的子树（因为题目要求返回第一个节点，中序遍历的第一个节点是最左子树），然后我们创建一个指针用来记录前驱节点，进入中序遍历函数后，当我们递归完左子树就开始修改链接关系了，先将当前节点的前驱链接上前驱节点（第一次正好将第一个节点的前驱链接置为nullptr）,然后判断前驱节点是否为空，如果不为空我们就可以将前驱节点的后继指针指向当前节点，修改链接关系后让我们的前驱节点变成当前节点，这样下一次递归后才能真正的记录前驱节点。我们画个示意图：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

我们仅仅演示了4到6的链接过程，不懂的小伙伴自己画递归图看看。

二、相对困难一点的二叉树OJ题

第一题：从前序与中序遍历序列构造二叉树

力扣链接：力扣

题目要求：

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

要构建二叉树首先要明白前序和中序的特点，首先前序遍历的第一个节点一定是根节点，然后我们在中序遍历中找到根节点，根节点的左边区间就是左子树，右边区间就是右子树，知道了这个我们就可以通过区间来构建二叉树了：

class Solution {
public:
    TreeNode* _buildTree(vector<int>& pre, vector<int>& in,int ibegin,int iend,int& pi)
    {
        if (ibegin>iend)
        {
            return nullptr;
        }
        TreeNode* root = new TreeNode(pre[pi]);
        int rooti = ibegin;
        while (rooti<=iend)
        {
            if (pre[pi]==in[rooti])
            {
                break;
            }
            else 
            {
                ++rooti;
            }
        }
        ++pi;
        root->left = _buildTree(pre,in,ibegin,rooti-1,pi);
        root->right = _buildTree(pre,in,rooti+1,iend,pi);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size()!=inorder.size())
        {
            return nullptr;
        }
        if (preorder.empty()||inorder.empty())
        {
            return nullptr;
        }
        int pi = 0;
        return _buildTree(preorder,inorder,0,inorder.size()-1,pi);
    }
};

首先我们需要判断前序的节点个数是否和中序的节点个数相等，如果连个数都不相等那么是无法构建二叉树的。如果两个序列中有一个为空或者同时为空，那么也是不能构建出来的。然后我们创建一个变量pi，这个变量用来记录前序中的根节点值的下标，我们要递归构建一颗二叉树需要知道中序的区间（因为每次从前序中拿到根节点需要在中序中寻找这个节点来划分左右区间），所以ibegin和iend用来记录区间下标，接下来进入函数，当begin==end的时候我们发现只有一个节点，这个时候就可以直接构建节点了，当begin小于end的时候构建需要递归左右子树，当begin大于end的时候就没有节点了需要返回空给上一个节点的左子树或者右子树。只要不满足递归返回要求，我们就先创建根节点，然后定义一个变量记录中序中根节点的位置，用这个下标分割出左子树和右子树，在创建当前节点的左子树之前一点要让记录根节点的下标pi++,左子树区间为[ibegin,rooti-1] 右子树区间为[rooti+1,iend]，左右子树链接完成返回当前节点即可，下面我们画一个递归图演示一下：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

第二题：从中序与后序遍历序列构造二叉树

力扣链接：力扣

题目要求：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

这道题和上一道题唯一的区别在于，后序遍历的最后一个节点是根，并且根据后序在中序找根是先从右子树然后才是左子树，下面我们代码实现一下：

class Solution {
public:
     TreeNode* _buildTree(vector<int>& in, vector<int>& post,int ibegin,int iend,int& pi)
    {
        if (ibegin>iend)
        {
            return nullptr;
        }
        TreeNode* root = new TreeNode(post[pi]);
        int rooti = ibegin;
        while (rooti<=iend)
        {
            if (post[pi]==in[rooti])
            {
                break;
            }
            else 
            {
                ++rooti;
            }
        }
        --pi;
        root->right = _buildTree(in,post,rooti+1,iend,pi);
         root->left = _buildTree(in,post,ibegin,rooti-1,pi);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
       if (inorder.size()!=postorder.size())
        {
            return nullptr;
        }
        if (inorder.empty()||postorder.empty())
        {
            return nullptr;
        }
        int pi = postorder.size()-1;
        return _buildTree(inorder,postorder,0,inorder.size()-1,pi);
    }
};

第三题：非递归实现二叉树的前序遍历

力扣链接：力扣

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

二叉树的递归实现前序遍历相信大家都会，那么非递归呢？其实非递归的思想也很简单，就是将根节点的所有左子树入栈并且同时将节点值放入数组，然后拿出栈顶元素用栈顶元素的右子树继续遍历，下面我们实现一下：

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

首先判断根节点是否为空，如果为空就返回空向量。我们用一个栈记录每次遍历的节点，cur去遍历子树，首先将树的所有子树入栈并且将节点的值入向量，然后看栈顶节点是否有右子树，有的话就遍历这个右子树，没有的话cur为空不进入小循环直接再次拿栈顶元素看是否有右子树，大循环的条件是当cur和栈不同时为空的时候进入循环，因为即使cur为空而栈不为空也说明有元素没有遍历完，下面我们画个图演示一下：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

第四题：非递归实现二叉树的中序遍历

力扣链接：力扣

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

中序遍历与前序遍历的区别在于，我们不能在遍历左子树的时候直接把节点的值入到向量中，而是等到出栈的时候在入，我们直接写代码：

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

第五题：非递归实现二叉树的后序遍历

力扣链接：力扣

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

后序遍历相对于前序和中序来讲就比较难了，后序的区别在于我们拿到栈顶元素的时候要判断这个栈顶元素是否有右子树，如果有我们需要直接入右子树的节点值不能直接弹出，并且我们无法知道到底是什么时候把根节点弹出栈，下面我们直接通过代码解释如何处理这个问题：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        if (root==nullptr)
        {
            return v;
        }
        stack<TreeNode*> st;
        TreeNode* cur= root;
        TreeNode* pre = nullptr;
        while (cur||!st.empty())
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* tmp = st.top();
            if (tmp->right==nullptr||tmp->right==pre)
            {
                st.pop();
                v.push_back(tmp->val);
                pre = tmp;
            }
            else 
            {
                cur =tmp->right;
            }
        }
        return v;
    }
};

下面我们通过画图解释一下：

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

通过上图我们可以看到，只有当栈顶节点的右子树为空或者栈顶节点的右子树等于上一个出栈的节点，那么就说明此时一个有右子树的根节点遍历完了，可以将这个根节点出栈了。

第六题：按之字形顺序打印二叉树

牛客网：按之字形顺序打印二叉树_牛客题霸_牛客网

题目要求：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

【C++】程序员的屠龙母鸡：二叉树进阶OJ题详解

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> vv;
        if (pRoot==nullptr)
        {
            return vv;
        }
        stack<TreeNode*> st;
        queue<TreeNode*> q;
        bool flag = true;
        st.push(pRoot);
        while (!st.empty())
        {
            int sz = st.size();
            vector<int> v;
            for (int i = 0;i<sz;i++)
            {
                TreeNode* tmp = st.top();
                st.pop();
                v.push_back(tmp->val);
                if (flag)
                {
                    if (tmp->left)
                    {
                        q.push(tmp->left);
                    }
                    if (tmp->right)
                    {
                        q.push(tmp->right);
                    }
                }
                else  
                {
                    if (tmp->right)
                    {
                        q.push(tmp->right);
                    }
                    if (tmp->left)
                    {
                        q.push(tmp->left);
                    }
                }
            }
            vv.push_back(v);
            while (!q.empty())
            {
                st.push(q.front());
                q.pop();
            }
            flag = !flag;
        }
        return vv;
    }
};

此题最重要的是控制左右子树入栈的顺序，因为是之字形所以第二层一定是从右向左的，而用队列刚好满足第一层到第二层的需求，那么后面的该如何控制呢？其实我们设置一个标志，满足这个标志就从左向右，不满足就从右向左入栈，然后我们要每次进入下一层遍历的时候将标志置为反，这样就实现每次都是相反方向。