经典二叉树面试题

痛定思痛。 2024-04-06 11:53 77阅读 0赞

#### 目录 ####

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

本篇博客方便自己复习当目录用，所以解析部分不是很完成，可以点击标题跳转链接去刷题！

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

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

> 二叉树具有天然的递归性;
> 
> 1.  根据规则，递归记录值之前和之后上’('和‘)’
> 2.  题目还要求特殊情况省略();
> 
> 一个根节点的left和right递归式无非就4种情况(非空 非空)，(空 空)，（非空，空），（空，非空），分类讨论即可

class Solution {
        
    public:
        string ret;
    
        void _tree2str(TreeNode* root)
        {
        
            //string插入int
            int tmp = root->val;
            ret+=to_string(tmp);//val可能为负，直接to_string方便转换成string
           
            if(root->left==nullptr&&root->right==nullptr)
            {
        
                return;
            }
            
            if(root->left==nullptr&&root->right!=nullptr)//右边有值,左边空不能省略()
            {
        
                ret+="()";
    
                ret+='(';
                _tree2str(root->right);
                ret+=')';
            }
    
            if(root->left!=nullptr&&root->right==nullptr)//省略右边()
            {
        
                ret+='(';
                _tree2str(root->left);
                ret+=')';
            }
            
            if(root->left!=nullptr&&root->right!=nullptr)
            {
        
                ret+='(';
                _tree2str(root->left);
                ret+=')';
                ret+='(';
                _tree2str(root->right);
                ret+=')';
            }
            
            
        }
        string tree2str(TreeNode* root) {
        
            //前序;根左右
            _tree2str(root);
            
            return ret;
        }
    };

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

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

> 经典题目，层序用队列，这个是变型版，**需要记录每一层的数量(当前qu的size)**;就可以把每层分开来存入数组！

class Solution {
        
    public:
        vector<vector<int>> levelOrder(TreeNode* root) {
        
            
           vector<vector<int>>ret;
           vector<int>tmp;
           if(!root) return ret;
           queue<TreeNode*>qu;
           qu.push(root);
           while(!qu.empty())//队列空的话就是没元素了，退出
           {
        
               tmp.clear();
               int len = qu.size();//配合下面的for循环 是解题核心
               for(int i = 0;i<len;i++){
        
                   TreeNode* cur = qu.front();
                   if(cur->left) qu.push(cur->left);
                   if(cur->right) qu.push(cur->right);
                   tmp.push_back(cur->val);
                   qu.pop();
               }
               ret.push_back(tmp);
           }
            return ret;
        }
    };

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

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

> 类似上题分层遍历,用queue，但是这个是要求倒着分层，先别想着stack，分层借助queue简单，别忘了C++有迭代器，reverse这些函数，观察以后直接把最终结果倒置一下不就好了;

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
            vector<vector<int>>ret;
            if(!root) return ret;
            vector<int>tmp;
            queue <TreeNode*>qu;
            qu.push(root);
            int len = qu.size();
            while(!qu.empty())
            {
        
                len = qu.size();//
                tmp.clear();          
                for(int i = 0;i<len;i++){
        //
                    TreeNode* cur = qu.front();
                    if(cur->left!=nullptr) qu.push(cur->left);
                    if(cur->right!=nullptr) qu.push(cur->right);
                    qu.pop();
                    tmp.push_back(cur->val);
                }
                ret.push_back(tmp);
                
            }
            reverse(ret.begin(),ret.end());//
            return ret;
        }   
    };

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

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

> 比较综合的一道题,我们可以想到搞两个数组把root到p，q的路径记录下来，再反向遍历偶遇到公共的root即可！
> 
> 既然要反向，那我们直接上stack;到时候去掉多余的长度以后，一起pop()到公共root即可！特殊情况已包含在内;

class Solution {
        
    public:
        stack<TreeNode*>a;
        stack<TreeNode*>b;
        stack<TreeNode*>tmp;
        //递归从root寻找p和q的路径,并保存
        void findpq(TreeNode* root, TreeNode*& p, TreeNode*& q)
        {
        
            tmp.push(root);
    
            if (root == p || root == q) {
        
                if (root == p) a = tmp;
                else b = tmp;
            }
    
            if (root->left) {
        //向左下方递归寻找
                findpq(root->left, p, q);
                tmp.pop();
            }
            if (root->right) {
        //向右下方递归寻找
                findpq(root->right, p, q);
                tmp.pop();
            }
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            //p，q都存入一个路径数组 最后从后往前找公共节点(祖先)//观察得:长的先走多于路径，之后一起走即可到达公共root
            findpq(root, p, q);
    
            int lena = a.size();
            int lenb = b.size();
            //从后向前,长的先把多余的长度走掉
            if (lena > lenb) {
        
                for (int i = 0; i < lena - lenb; i++) {
        
                    a.pop();
                }
            }
            else {
        
                for (int i = 0; i < lenb - lena; i++) {
        
                    b.pop();
                }
            }
            //一起走 遇到公共root
            for (int i = 0; !a.empty(); i++) {
        
    
                if (a.top() == b.top()) return a.top();
                else {
        
                    a.pop();
                    b.pop();
                }
            }
            return nullptr;
    
        }
    };

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

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

> 看到二叉搜索树 和排好序的结果，那么一定是中序遍历了！;  
> 可以看到中序遍历完美的排好了序，我们要做的就是在这个过程中，对每个节点动动手脚;  
> 分析得:只要能记录中序遍历中，每个cur节点的前驱prev，那么用prev->right = cur,cur->left = prev就构建双向链表了;单向同理;之后再把从最左节点开始构建考虑进去，传入prev == nullptr，构建的时候判断下prev 就能满足从最左结点开始构建了;  
> 中序中一个节点构建完，更新prev为cur，进行下个结点的构建

class Solution {
        
    public:
        void _treeToDoublyList(Node*cur,Node*& prev)
        {
        
            if(!cur)return;
            _treeToDoublyList(cur->left,prev);
            //中序遍历并且：前驱的右指向cur cur的左指向前驱;
            if(prev) prev->right = cur;
            if(prev) cur->left = prev;
            prev = cur;//精髓更新prev
    
            _treeToDoublyList(cur->right,prev);
        }
        Node* treeToDoublyList(Node* root) {
        
            if(!root) return nullptr;
    
            //记录最左最右 方便最后链表改造循环;
            Node* _left = root;
            Node* _right = root;
            Node* prev = nullptr;
            while(_left->left) _left = _left->left;
            while(_right->right) _right = _right->right;
    
            _treeToDoublyList(root,prev);
    
            _left ->left= _right;
            _right->right = _left;
            
            return _left;
        }
    };

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

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

> 这种题有两种:  
> 根据前序+中序历的数值，构建二叉树;  
> 根据后续+中序遍历的数值，构建二叉树;  
> 核心思想，二叉树的三种遍历特征+分治；  
> 根据前序(根左右)or 后序(左右根)**确定即将构建的根**， **在中序遍历数组中找到当前根确定左右分支区间下标**，之后**分治构建**左子树+右子树 or 右子树+左子树

class Solution {
        
    	int index_root;//全局变量！确定下个构建的根在前序数组中的下标
    public:
        TreeNode* _build(vector<int>& preorder,vector<int>& inorder,int l2,int r2)
        {
        
            if(l2>r2) return nullptr;
            int iroot = preorder[l1];
            TreeNode* root = new TreeNode(iroot);
    
            int i = l2;
            for(;i<r2;i++){
        //再inorder中找到当前根对应的位置，方便之后划分左右区间,进一步分治构建
                if(inorder[i] == iroot) break;//l2 i-1 --iroot-- i+1 r2
            }
            index_root++;//注意这个index_root是确定当前构建root的位置，搞的全局变量，不然回来的时候index会重复,则重复使用构建过的root
            
            //前序(根 左 右) 那么构建完根之后，先构建左子树，再构建右子树;    后序(左 右 根),倒着相当于(根 右 左)则构建root 再构建右 再构建左子树即可;
            root->left =  _build(preorder,inorder,l2,i-1);
            root ->right =  _build(preorder,inorder,i+1,r2);
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
    
            index_root= 0;//
            return  _build(preorder,inorder,0,inorder.size() - 1);
        }
    };

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

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

class Solution {
        
        int index_root;//全局变量,后序数组中根的下标
    public:
        
        TreeNode* _build(vector<int>& inorder,int l1, int r1,vector<int>& postorder){
        
            if(l1>r1) return nullptr;
    
            int iroot = postorder[index_root];
            TreeNode* root = new TreeNode(postorder[r2]);
            
            int i = l1;
            for(;l1<r1;i++){
        
                if(inorder[i] == iroot) break;
            }
            index_root--;
            //后序，倒着左右根倒着就是根右左，则先构建先右子树 再左子树
            root->right = _build(inorder,i+1,r1,postorder);
            root->left = _build(inorder,l1,i-1,postorder);
    
            return root;
        }
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        
        
            index_root= postorder.size()-1;
            return _build(inorder,0,inorder.size()-1,postorder);
        }
    };

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

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

> 二叉树的表利用递归很好写，一般面试会让写非递归;
> 
> 非递归相比递归，就是将递归所隐式维护的栈，通过一个stack类型拿出来了 配合while循环控制"递归顺序";,主要思路其实都一样,递归分治思想;
> 
> **使用双while循环结构，不断地循环模拟递归情况！**

class Solution {
        
    public:
        vector<int> preorderTraversal(TreeNode* root) {
        
            //根 左 右
            stack<TreeNode*>st;
            vector<int>ret;
            if(!root) return ret;
            while(!st.empty()||root)// ||root的原因：比如1 2 3树,该递归右子树了，此时root = 3 但是st是空！这种还是需要进入循环操作的;
            {
        
                while(root)
                {
        
                    ret.push_back(root->val);//出根
                    st.push(root);//递归左
                    root = root->left;
                }
                //递归右
                root = st.top()->right;
                st.pop();     
            }
            return ret;
        }
    };

### 二叉树的中序遍历非递归 ###

class Solution {
        
    public:
        vector<int> inorderTraversal(TreeNode* root) {
        
            //左 根 右
            vector<int>ret;
            stack<TreeNode*>st;
            if(!root) return ret;
    
            while(!st.empty()||root)
            {
        
                while(root)
                {
        
                    st.push(root);
                    root = root->left;//递归左
                }
                TreeNode* tmp = st.top();
                ret.push_back(tmp ->val);//出根
                root = tmp->right;//递归右
                st.pop();
            }
            return ret;
        }
    };

类似于上题的前序遍历;

### [二叉树的后序遍历非递归][Link 8] ###

> 后序是 左 右 root,需要递归完全部的左子树和右子树才能出当前节点;因此跟前，中序不太一样，并且更有难度！一般就考这个！
> 
> **核心**:我们需要一个node***prev**,来**记录上次出的节点*\*;
> 
> 先递归左子树到底之后，**检查右子树**:每当当前节点的右子树root->right == prev ||nullptr(叶子节点)的时候，**就出**当前节点root并更新prev，**否则**就是当前节点root的右子树还没被递归，则递归他;

class Solution {
        
    public:
        vector<int> postorderTraversal(TreeNode* root) {
        
            //左 右 根
            vector<int>ret;
            stack<TreeNode*>st;
            TreeNode* prev = nullptr;//引入prev节点，判断当前root的右子树有没有递归过，递归过:那root就该出来了;没递归过:递归;
            if(!root) return ret;
            
            while(!st.empty()||root){
        
                
                while(root){
        
                    st.push(root);
                    root = root->left;//递归左
                }
    
                TreeNode* tmp = st.top();
                if(tmp->right == prev||tmp->right==nullptr){
        //叶子节点不用跟prev比，右边是nullptr直接出根;
                    ret.push_back(tmp->val);//出根
                    st.pop();
                    prev = tmp;//更新prev;
                }   
                else{
        
                    root = tmp->right;//递归右;  
                }
                
            }
            return ret;
        }
    };

[Link 1]: https://leetcode.cn/problems/construct-string-from-binary-tree/
[1fd0e8e258544e87bf40b6a529e0c098.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a55f6d4deea848e48843931102318a03.png
[Link 2]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[b3b231a415344eee9139f7c9db31d8bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/96b55039321c4f50a9259e6a2a8bf587.png
[2]: https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
[44e33d6858f841a9812f85ec0acdb19b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8cd8dbec853c41128c2ac5bc7aafc8d3.png
[Link 3]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[b3c7f628440a417db7c006d8e5665966.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/42815d04fdc84e22abd8f201d98e8e1e.png
[Link 4]: https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
[080ee8eeae9b464e91d1288387115c6d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/80ec5304b5fa499fa029894adbb181dc.png
[Link 5]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[67a9bfebffc04acfbea9aba9bbee8197.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/74adb283548241d4b0dfefa9597591b2.png
[Link 6]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[dcb68d34a1f6489ba4434a139f173a9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/3770114fe31840b5b22ea73c48abcf20.png
[Link 7]: https://leetcode.cn/problems/binary-tree-preorder-traversal/
[d12c6bb08f6e4d38a4632e0bf878f171.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a10470a91b3d45b88ead8f6105992fae.png
[Link 8]: https://leetcode.cn/problems/binary-tree-postorder-traversal/