当前位置：首页 > article >正文

C++：二叉树进阶面试题

article 2025/1/10 21:01:49

文章目录

前言
一、根据二叉树创建字符串
二、二叉树的层序遍历
三、二叉树的最近公共祖先
四、二叉搜索树与双向链表
五、从前序与中序遍历序列构造二叉树
六、从中序与后序遍历序列构造二叉树
七、二叉树的前序遍历，非递归迭代实现
八、二叉树中序遍历，非递归迭代实现
九、二叉树的后序遍历，非递归迭代实现

前言

学完二叉树进阶之后，我们一起来看一看二叉树进阶的面试题~

这些题目更适合使用C++完成，难度也更大一些。

在这里插入图片描述

一、根据二叉树创建字符串

根据二叉树创建字符串

在这里插入图片描述

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;
    }
};

二、二叉树的层序遍历

二叉树的层序遍历

在这里插入图片描述

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> ret;
        if (root == nullptr) return ret;

        queue<TreeNode*> q;

        q.push(root);
        while (!q.empty())
        {
            int count = q.size();
            ret.push_back(vector<int> ());
            for (int i = 0; i < count; i++)
            {
                TreeNode* tmp = q.front();
                q.pop();
                ret.back().push_back(tmp->val);
                if (tmp->left) q.push(tmp->left);
                if (tmp->right) q.push(tmp->right);
            }
        }

        return ret;
    }
};

三、二叉树的最近公共祖先

二叉树的最近公共祖先

在这里插入图片描述

class Solution {
public:

    bool Find(TreeNode* root, TreeNode* x)
    {
        if (root == nullptr) return false;

        return root == x
        || Find(root->left, x)
        || Find(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if (root == nullptr) return nullptr;
        if (root == p || root == q) return root;

        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;

        qInLeft = Find(root->left, q);
        qInRight = !qInLeft; 

        if (pInLeft && qInLeft) return lowestCommonAncestor(root->left, p, q);
        else if (pInRight && qInRight) return lowestCommonAncestor(root->right, p, q);
        else return root;

    }
};

在这里插入图片描述

class Solution {
public:

    bool Findpath(TreeNode* root, TreeNode* x, stack<TreeNode*>& s)
    {
        if (root == nullptr) return false;

        s.push(root);

        if (s.top() == x) return true;

        if (Findpath(root->left, x, s)) return true;

        if (Findpath(root->right, x, s)) return true;

        s.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        stack<TreeNode*> ppath, qpath;
        Findpath(root, p, ppath);
        Findpath(root, q, qpath);

        while (ppath.size() > qpath.size())
            ppath.pop();
        while (ppath.size() < qpath.size())
            qpath.pop();
        
        while (ppath.top() != qpath.top())
        {
            ppath.pop();
            qpath.pop();
        }

        return ppath.top();
    }
};

四、二叉搜索树与双向链表

二叉搜索树与双向链表

在这里插入图片描述

class Solution 
{
public:

    void Inorder(TreeNode* cur, TreeNode*& prev)
	{
		if (cur == nullptr) return;
		
		Inorder(cur->left, prev);

		cur->left = prev;
		if (prev)
		    prev->right = cur;

		prev = cur;

		Inorder(cur->right, prev);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) 
	{
        TreeNode* prev = nullptr;

		Inorder(pRootOfTree, prev);

		TreeNode* headret = pRootOfTree;
		while (headret && headret->left)
		{
			headret = headret->left;
		}

		return headret;
    }
};

五、从前序与中序遍历序列构造二叉树

从前序与中序遍历序列构造二叉树
在这里插入图片描述

在这里插入图片描述

class Solution {
public:

    TreeNode* _build(vector<int>& preorder, vector<int>& inorder
                    , int& index, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;

        TreeNode* root = new TreeNode(preorder[index]);

        int rooti = inbegin;
        while (rooti != inend)
        {
            if (inorder[rooti] == preorder[index])
            {
                break;
            }
            rooti++;
        }

        index++;
        root->left = _build(preorder, inorder, index, inbegin, rooti - 1);
        root->right = _build(preorder, inorder, index, rooti + 1, inend);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int index = 0;
        int inbegin = 0, inend = preorder.size() - 1;

        TreeNode* ret = _build(preorder, inorder, index, inbegin, inend);

        return ret;
    }
};

六、从中序与后序遍历序列构造二叉树

从中序与后序遍历序列构造二叉树
在这里插入图片描述

在这里插入图片描述

class Solution {
public:

    TreeNode* _build(vector<int>& inorder, vector<int>& postorder
                    , int& index, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;

        TreeNode* root = new TreeNode(postorder[index]);

        int rooti = inbegin;
        while (rooti != inend)
        {
            if (inorder[rooti] == postorder[index])
                break;

            rooti++;
        }

        index--;
        root->right = _build(inorder, postorder, index, rooti + 1, inend);
        root->left = _build(inorder, postorder, index, inbegin, rooti - 1);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        int index = postorder.size() - 1;
        int inbegin = 0, inend = inorder.size() - 1;

        TreeNode* ret = _build(inorder, postorder, index, inbegin, inend);

        return ret;
    }
};

七、二叉树的前序遍历，非递归迭代实现

二叉树的前序遍历，非递归迭代实现

在这里插入图片描述

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> s;
        TreeNode* cur = root;
        vector<int> ret;

        // 当前结点不为空 或 栈不为空（去右子树）循环
        while (cur || !s.empty())
        {
            while (cur)
            {
                // 前序遍历，先根
                ret.push_back(cur->val);
                // 入栈——为了去找右子树
                s.push(cur);
                cur = cur->left;
            }

            // 依次访问结点的右子树，利用了栈的先进先出
            TreeNode* tmp = s.top();
            s.pop();

            // 以子问题的方式解决右子树
            cur = tmp->right;
        }

        return ret;
    }
};

八、二叉树中序遍历，非递归迭代实现

二叉树中序遍历，非递归迭代实现

在这里插入图片描述

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> s;
        TreeNode* cur = root;
        vector<int> ret;

        // 当前结点不为空 或 栈不为空（去右子树）循环
        while (cur || !s.empty())
        {
            while (cur)
            {
                // 入栈——为了去找右子树
                s.push(cur);
                cur = cur->left;
            }

            // 依次访问结点的右子树，利用了栈的先进先出
            TreeNode* tmp = s.top();
            s.pop();
            // 中序遍历，先左后根
            ret.push_back(tmp->val);

            // 以子问题的方式解决右子树
            cur = tmp->right;
        }

        return ret;
    }
};

九、二叉树的后序遍历，非递归迭代实现

二叉树的后序遍历，非递归迭代实现

在这里插入图片描述

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        stack<TreeNode*> s;
        TreeNode* cur = root;
        //记录上一次访问的结点
        TreeNode* prev = nullptr;
        vector<int> ret;

        // 当前结点不为空 或 栈不为空（去右子树）循环
        while (cur || !s.empty())
        {
            while (cur)
            {
                // 入栈——为了去找右子树
                s.push(cur);
                cur = cur->left;
            }
            
            TreeNode* tmp = s.top();
            // 先不要着急pop
            
            if (tmp->right == nullptr || tmp->right == prev)
            {
                // 更新前驱，也就是我们上一个访问的结点
                prev = tmp;
                // 这种情况代表没有右子树，或者右子树已经访问过了，可以直接访问当前结点
                ret.push_back(tmp->val);
                // 当前结点遍历了，才能pop
                s.pop();
            }
            else
            {
                // 走到这里代表右子树没有访问，解决右子树
                cur = tmp->right;
            }
        }    

        return ret;
    }
};