【C++】二叉搜索树经典OJ题目

浅浅的花香味﹌ 2023-09-26 22:12 118阅读 0赞

#### 文章目录 ####

*  根据二叉树创建字符串
 *  二叉树的层序遍历
 *  二叉树的层序遍历II
 *  二叉树的最近公共祖先
 *  二叉搜索树与双向链表
 *  从前序与中序遍历序列构造二叉树
 *  从中序与后序遍历序列构造二叉树
 *  二叉树的前序遍历(非递归)
 *  二叉树的中序遍历(非递归)
 *  二叉树的后序遍历(非递归)

## [根据二叉树创建字符串][Link 1] ##

> ![在这里插入图片描述][07b4e42828ac415da7f05e6d22f2b62e.png]

**解题思路**

这道题是让我们使用前序遍历的方式来创建字符串，但是有一点需要注意的是，再创建的字符串中，需要将每一个左右子树用括号括起来。这里扩括号的时候有两点需要注意的细节：

>  *  当左右子树都为空时，该节点左右子树的括号都可以省略掉。
>  *  当左子树不为空，右子树为空时，省略掉右子树的括号。
>  *  当左子树为空，右子树不为空时，左子树的括号不能省略掉。

**代码实现**

class Solution {
        
    public:
        string tree2str(TreeNode* root) {
        
            if(root == nullptr)
                return "";
            string 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;
        }
    };

![在这里插入图片描述][4548e02cd3cf4023afcffbb8ded7881b.png]

--------------------

## [二叉树的层序遍历][Link 2] ##

> ![在这里插入图片描述][47439139f9484bfca59aaf90f7e98691.png]

**解题思路**

首先，定义一个队列`q`、记录当前层节点个数的变量`levelnum`和`vector <vector < int > >`来存储遍历后的结果。 然后判断根节点是不是空， 如果不是空先将根节点入队列，然后`levelnum`置为1。

外层循环控制队列是否为空，如果为空，则说明节点已经全部出队。该树也已经被访问完了。内层循环来控制每一层节点的个数，然后在队列中按照对头——对尾的顺序依次访问队列中的每一个节点，每访问一个节点，就让该节点出队，并让该节点的左右非空孩子节点入队，这样一来，上一层的节点全部出队后，下一层的节点也就全部入队了。内层循环每循环完一次，就将新队列中的元素个数赋给`levelnum`。这样每一层的节点就被依次插入二维数组中的每一行中了。

**代码实现**

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            vector<vector<int>> vv;
            queue<TreeNode*> q;
            int levelnum = 0;
            if(root){
        
                q.push(root);
                levelnum = 1;
            }
            while(!q.empty())
            {
        
                vector<int> v;
                while(levelnum--)
                {
        
                    TreeNode* tmp = q.front();
                    v.push_back(tmp->val);
                    q.pop();
                    if(tmp->left)
                        q.push(tmp->left);
                    if(tmp->right)
                        q.push(tmp->right);
                }
                vv.push_back(v);
                levelnum = q.size();
            }
            return vv;
        }
    };

![在这里插入图片描述][ae6ec3d4645b46eea2dbbe5f3ede15b6.png]

--------------------

## 二叉树的层序遍历II ##

> ![在这里插入图片描述][4df42d8d05b04f51b9eaf6965aef98a5.png]

**解题思路**

这道题目和上一道题的不同点在于：上一道题目是从上到下依次遍历每一层的元素，这道题是从下到上依次遍历每一层。所以对于这道题目，我们只需要将上一道题目的代码拷贝过来，然后将结果逆置一下就可以了。

**代码实现**

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            queue<TreeNode*> q;
            vector<vector<int>> vv;
            int levelSize = 0;
            if(root)
            {
        
                q.push(root);
                levelSize = 1;
            }
            while(!q.empty())
            {
        
                vector<int> v;
                while(levelSize--)
                {
        
                    TreeNode* tmp = q.front();
                    v.push_back(tmp->val);
                    if(tmp->left) q.push(tmp->left);
                    if(tmp->right) q.push(tmp->right);
                    q.pop();
    
                }
                vv.push_back(v);
                levelSize = q.size();
            }
            return vv;
        }
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
            vector<vector<int>> vv = levelOrder(root);
            reverse(vv.begin(),vv.end());
            return vv;
        }
    };

![在这里插入图片描述][437abdea0a2d4cec8730f82ab7f8bd5f.png]

--------------------

## [二叉树的最近公共祖先][Link 3] ##

> ![在这里插入图片描述][9131e5d1ee8748b4acc411bc738beee8.png]

**解题思路**

先定义两个栈，用来存储从`根节点到p`和`从根节点到q`的路径，将他们的路径中的每一个节点存储到栈中。我们需要找的就是这两条路径中相同的那个节点。也就是我们需要先控制栈中的元素个数相同，然后再比较栈顶的元素是否相同，如果不相同则同时弹出两个栈中栈顶的元素，直到两个栈中栈顶的元素相同，此时栈顶的元素就是我们要找的公共祖先。

**代码实现**

class Solution {
        
    public:
        //定义两个栈，找到两个节点的路径，压入栈中
        bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path)
        {
        
            //节点为空，直接返回false
            if(root == nullptr)
                return false;
            //节点不为空
            path.push(root);
            if(root == x)
                return true;
            if(GetPath(root->left,x,path))
                return true;
            if(GetPath(root->right,x,path))
                return true;
            path.pop();
            return false;        
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            stack<TreeNode*> pPath,qPath;
            GetPath(root,p,pPath);
            GetPath(root,q,qPath);
            while(pPath.size() != qPath.size())
            {
        
                if(pPath.size() > qPath.size())
                    pPath.pop();
                else
                    qPath.pop();
            }
            while(pPath.top() != qPath.top())
            {
        
                pPath.pop();
                qPath.pop();
            }
            return pPath.top();
        }
    };

![在这里插入图片描述][0b7f86be738942faac5772aefecce2de.png]

--------------------

## [二叉搜索树与双向链表][Link 4] ##

> ![在这里插入图片描述][bb0167b50f684a7f8d0079e0297e4746.png]

**解题思路**

当前节点的指针用`cur`表示，再定义一个`prev`指针，让prev来表示当前节点cur的前一个结点，这样通过不断递归的方式访问每一个节点之后就可以将二叉树转换成双向循环链表了。这里我们需要注意的是，`prev`一定要使用引用传参，因为每一层节点的prev都是上一次函数调用的cur。

**代码实现**

class Solution {
        
    public:
        void InOrderConvert(Node* cur, Node* &prev)
    	{
        
    		if(cur == nullptr)
    			return;
    		InOrderConvert(cur->left, prev);
    		cur->left = prev;
    		if(prev)
    			prev->right = cur;
    		prev = cur;
    		InOrderConvert(cur->right, prev);
    	}
        Node* treeToDoublyList(Node* root) {
        
            if(root == nullptr) return nullptr;
            Node* prev = nullptr;
    		InOrderConvert(root, prev);
    
    		Node* cur = root;
    		while(cur && cur->left)
    		{
        
    			cur = cur->left;
    		}
            Node* Rcur = root;
            while(Rcur && Rcur->right)
            {
        
                Rcur = Rcur->right;
            }
            cur->left = Rcur;
            Rcur->right = cur;
    		return cur;
        }
    };

![在这里插入图片描述][b0917f201a7649b790efcee2417a262b.png]

--------------------

## [从前序与中序遍历序列构造二叉树][Link 5] ##

> ![在这里插入图片描述][9bee9dcfe7c24151b53f7a0f431fcc04.png]

**解题思路**

大思路很简单，但是这道题目写起来却不是很容易，通过前序我们可以找到根节点，中序分割出左右子树，如果区间还存在说明还有节点未构建完，如果区间不存在说明已经没有节点可以构建，直接返回空。

**代码实现**

class Solution {
        
    public:
        TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& prei, int begin,int end) 
        {
        
            if(begin > end)
                return nullptr;
            //创建根节点
            TreeNode* newnode = new TreeNode(preorder[prei]);
            
            //分割左右子区间
            int rooti = begin;
            while(rooti <= end)
            {
        
                if(inorder[rooti] == preorder[prei])
                    break;
                else 
                    rooti++;
            }
            prei++;
            //递归创建左右子树
            newnode->left = _buildTree(preorder, inorder, prei, begin, rooti - 1);
            newnode->right = _buildTree(preorder, inorder, prei, rooti + 1, end);
            return newnode;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
            int i = 0;
            return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
        }
    };

![在这里插入图片描述][43bc6d1699d4445eb8a1d21abc9a1732.png]

--------------------

## [从中序与后序遍历序列构造二叉树][Link 6] ##

> ![在这里插入图片描述][71e0d1fca830436d8cb25009fc21c901.png]

**解题思路**

因为后续序列和前序序列有一点点不同，所以这里我们必须从后往前依次访问后序序列中的每一个元素，这样才能找出每一棵子树的根节点并从中序将左右子区间分割开。这里和前序不一样的是，这里我们需要先构建右子树，在构建左子树，最后将根节点和左右子树链接起来。

**代码实现**

class Solution {
        
    public:
        TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int &pos, int begin, int end)
        {
        
            if(begin > end)
                return nullptr;
            TreeNode* newnode = new TreeNode(postorder[pos]);
            int rooti = begin;
            while(rooti <= end)
            {
        
                if(postorder[pos] == inorder[rooti])
                    break;
                else
                    rooti++;
            }
            pos--;
            //分割左右子区间
    
            newnode->right = _buildTree(inorder, postorder, pos, rooti + 1, end);
            newnode->left = _buildTree(inorder, postorder, pos, begin, rooti - 1);
            return newnode;
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
            int i = postorder.size() - 1;
            return _buildTree(inorder, postorder, i, 0, postorder.size() - 1);
        }
    };

![在这里插入图片描述][3408ad2e761d412eaa740db4d7e82d41.png]

--------------------

## [二叉树的前序遍历(非递归)][Link 7] ##

> ![在这里插入图片描述][067c23bd511a427ca3d8c8e7de49500c.png]

**解题思路**

前序遍历的顺序是根、左子树、右子树。因此最后我们遍历整棵树的时候，一定是先访问左路节点，然后访问左路节点的右子树，左路节点的右子树又可以看作一棵二叉树、然后继续二叉子树的前序遍历，最后直到遍历访问整棵二叉树。

我们需要定义一个栈`st`、一个`vector v` 和一个 `TreeNode* cur`，`cur`初始化为`root`。定义一个while循环，循环结束的条件是cur不为空，或者st不为空，首相我们先将左路节点依次插入栈中，同时也将左路节点插入到vector中，这时左路节点就已经访问完了，然后将栈顶元素保存下来并出栈，并将cur指向栈顶元素的右子树，做像上面一样的操作。这样就能保证每棵子树都能够按照根——左子树——右子树的顺序访问每一个节点，最后遍历整棵树就能达到预期的结果。

**代码实现**

class Solution {
        
    public:
        vector<int> preorderTraversal(TreeNode* root) {
        
            TreeNode* cur = root;
            vector<int> v;
            stack<TreeNode*> st;
            while(cur || !st.empty())
            {
        
                while(cur)
                {
        
                    v.push_back(cur->val);
                    st.push(cur);
                    cur = cur->left;
                }
                //访问每个根节点的右子树
                TreeNode* tmp = st.top();
                st.pop();
                cur = tmp->right;
            }
            return v;
        }
    };

![在这里插入图片描述][00bd40962f304a3380cf8529125d91fa.png]

--------------------

## [二叉树的中序遍历(非递归)][Link 8] ##

> ![在这里插入图片描述][577138e5a3fd4e1fb4fa115a154a3770.png]

**解题思路**

中序遍历的思路和前序遍历的思路也差不多，有一点不同的就是中序遍历的顺序是左子树——根——右子树，和前序遍历一样，先将根节点入栈，不同的是入栈的同时不能访问节点，等到左路节点全部入栈后，先将该节点保存，然后访问该节点并将该节点弹出栈，然后将cur指向该节点的右子树。然后while循环中重复和前序遍历一样的操作。

**代码实现**

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

![在这里插入图片描述][5be55273742f42609dadbde3aaeb0994.png]

--------------------

## [二叉树的后序遍历(非递归)][Link 9] ##

> ![在这里插入图片描述][c2aac47fa55c4598a556f20f4a5c8539.png]

**解题思路**

后序遍历的顺序是左子树——右子树——根，所以我们在访问根节点的时候必须保证左子树和右子树都已经被访问过了才行。同样，和上面的思路一样，我们同样是先将左路节点入栈并且不访问，当左路节点全部入栈后。取栈顶元素，这时我们需要先判断该节点是否有右子树，或者该节点的右子树是否被访问过。判断该节点的右子树是否被访问过的方法是：设置一个指针 **prev** 来记录前一个访问过的节点，因为只有右子树访问完才能访问根节点，所以我们只需要判断该节点的右子树是否是上一个访问过的节点就可以了。 同时，如果右子树为空也能直接访问该节点。

**代码实现**

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

![在这里插入图片描述][c78835bcba764cae982d617e4fb47fc4.png]

--------------------

[Link 1]: https://leetcode.cn/problems/construct-string-from-binary-tree/
[07b4e42828ac415da7f05e6d22f2b62e.png]: https://img-blog.csdnimg.cn/07b4e42828ac415da7f05e6d22f2b62e.png
[4548e02cd3cf4023afcffbb8ded7881b.png]: https://img-blog.csdnimg.cn/4548e02cd3cf4023afcffbb8ded7881b.png
[Link 2]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[47439139f9484bfca59aaf90f7e98691.png]: https://img-blog.csdnimg.cn/47439139f9484bfca59aaf90f7e98691.png
[ae6ec3d4645b46eea2dbbe5f3ede15b6.png]: https://img-blog.csdnimg.cn/ae6ec3d4645b46eea2dbbe5f3ede15b6.png
[4df42d8d05b04f51b9eaf6965aef98a5.png]: https://img-blog.csdnimg.cn/4df42d8d05b04f51b9eaf6965aef98a5.png
[437abdea0a2d4cec8730f82ab7f8bd5f.png]: https://img-blog.csdnimg.cn/437abdea0a2d4cec8730f82ab7f8bd5f.png
[Link 3]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[9131e5d1ee8748b4acc411bc738beee8.png]: https://img-blog.csdnimg.cn/9131e5d1ee8748b4acc411bc738beee8.png
[0b7f86be738942faac5772aefecce2de.png]: https://img-blog.csdnimg.cn/0b7f86be738942faac5772aefecce2de.png
[Link 4]: https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
[bb0167b50f684a7f8d0079e0297e4746.png]: https://img-blog.csdnimg.cn/bb0167b50f684a7f8d0079e0297e4746.png
[b0917f201a7649b790efcee2417a262b.png]: https://img-blog.csdnimg.cn/b0917f201a7649b790efcee2417a262b.png
[Link 5]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[9bee9dcfe7c24151b53f7a0f431fcc04.png]: https://img-blog.csdnimg.cn/9bee9dcfe7c24151b53f7a0f431fcc04.png
[43bc6d1699d4445eb8a1d21abc9a1732.png]: https://img-blog.csdnimg.cn/43bc6d1699d4445eb8a1d21abc9a1732.png
[Link 6]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[71e0d1fca830436d8cb25009fc21c901.png]: https://img-blog.csdnimg.cn/71e0d1fca830436d8cb25009fc21c901.png
[3408ad2e761d412eaa740db4d7e82d41.png]: https://img-blog.csdnimg.cn/3408ad2e761d412eaa740db4d7e82d41.png
[Link 7]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[067c23bd511a427ca3d8c8e7de49500c.png]: https://img-blog.csdnimg.cn/067c23bd511a427ca3d8c8e7de49500c.png
[00bd40962f304a3380cf8529125d91fa.png]: https://img-blog.csdnimg.cn/00bd40962f304a3380cf8529125d91fa.png
[Link 8]: https://leetcode.cn/problems/binary-tree-inorder-traversal/
[577138e5a3fd4e1fb4fa115a154a3770.png]: https://img-blog.csdnimg.cn/577138e5a3fd4e1fb4fa115a154a3770.png
[5be55273742f42609dadbde3aaeb0994.png]: https://img-blog.csdnimg.cn/5be55273742f42609dadbde3aaeb0994.png
[Link 9]: https://leetcode.cn/problems/binary-tree-postorder-traversal/
[c2aac47fa55c4598a556f20f4a5c8539.png]: https://img-blog.csdnimg.cn/c2aac47fa55c4598a556f20f4a5c8539.png
[c78835bcba764cae982d617e4fb47fc4.png]: https://img-blog.csdnimg.cn/c78835bcba764cae982d617e4fb47fc4.png