2024-06-01 17:00 聯(lián)發(fā)科技_智慧產(chǎn)品軟件開(kāi)發(fā)部_Android BSP

關(guān)注

嵌入式軟件常用面試題匯總之 C/C++ 語(yǔ)言相關(guān)(6)

C/C++之?？?span id="npdgxvi1zkhb" class="js-mobile-large" style="color: rgb(245,34,45);font-size: 16.0px;">二叉樹(shù)相關(guān)基礎(chǔ)編程題匯總

嵌入式的筆試中編程題也會(huì)有基礎(chǔ)的二叉樹(shù)相關(guān)操作題，以下挑幾道當(dāng)時(shí)做過(guò)比較基礎(chǔ)重要的，掌握了基本就能通關(guān)，至少掌握幾種遍歷的寫(xiě)法。參考的解法都是幾年前自己做的了，也歡迎各位優(yōu)化指正！

1.二叉樹(shù)的層序遍歷

給你二叉樹(shù)的根節(jié)點(diǎn)?root?，返回其節(jié)點(diǎn)值的?層序遍歷?。（即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]

示例 2：

輸入：root = [1]
輸出：[[1]]

示例 3：

輸入：root = []
輸出：[]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[0, 2000]?內(nèi)
-1000 <= Node.val <= 1000

解法參考：

/**
 * 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>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> result;
        vector<int> tmp;
        if(root == NULL) return result;
        queue<TreeNode*> T;
        T.push(root);
        int size = 0;
        while(!T.empty())
        {   
            size = T.size();
            while(size)
            {
                root = T.front();
                T.pop();
                tmp.push_back(root->val);                
                if(root->left != NULL)
                {
                    //tmp.push_back(root->left->val);
                    T.push(root->left);
                }
                if(root->right != NULL)
                {
                    //tmp.push_back(root->right->val);
                    T.push(root->right);
                }       
                --size;
            }
            result.push_back(tmp);
            tmp.clear();
        }
        return result;    
    }
};

2.二叉樹(shù)的前序遍歷

給你二叉樹(shù)的根節(jié)點(diǎn)?root?，返回它節(jié)點(diǎn)值的?前序遍歷。

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,2,3]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

示例 4：

輸入：root = [1,2]
輸出：[1,2]

示例 5：

輸入：root = [1,null,2]
輸出：[1,2]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100

參考解法：直接利用棧來(lái)完成，比較方便理解。

/**
 * 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) {}
 * };
 */

/*
二叉樹(shù)的前序遍歷是一種深度優(yōu)先遍歷方式,前序遍歷的順序是：
1.訪問(wèn)根節(jié)點(diǎn)。
2.前序遍歷左子樹(shù)。
3.前序遍歷右子樹(shù)。
下面的解法跟遞歸本質(zhì)一樣，不過(guò)是把棧給顯示出來(lái)了。
*/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
            stack<TreeNode*> TreeStack;
            vector<int> result;
            while(root != NULL || !(TreeStack.empty()))
            {
                while(root != NULL)
                {
                   result.push_back(root->val);
                   TreeStack.push(root);
                   root = root->left;         
                }
                root = TreeStack.top();
                TreeStack.pop();
                root = root->right;
            }
            return result;    
    }
};

3.二叉樹(shù)的中序遍歷

給定一個(gè)二叉樹(shù)的根節(jié)點(diǎn)?root?，返回?它的?中序?遍歷?。

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,3,2]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100

解法參考：

/**
 * 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) {}
 * };
 */

/*
中序遍歷的順序是：左子樹(shù) -> 根節(jié)點(diǎn) -> 右子樹(shù)
*/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> TreeStack;  //棧來(lái)輔助遍歷
        while(root != NULL || !(TreeStack.empty()))  //確保了所有節(jié)點(diǎn)都會(huì)被訪問(wèn)到
        {
            while(root != NULL)  //內(nèi)部循環(huán)用于遍歷到最左邊的節(jié)點(diǎn)，將遍歷路徑中的所有節(jié)點(diǎn)壓入棧中
            {
                TreeStack.push(root);
                root = root->left;
            }
  //從棧中彈出一個(gè)節(jié)點(diǎn)，并將其值添加到結(jié)果向量中。這一步對(duì)應(yīng)中序遍歷中的“訪問(wèn)根節(jié)點(diǎn)”步驟。
            root = TreeStack.top();
            TreeStack.pop(); 
            result.push_back(root->val);
//轉(zhuǎn)向當(dāng)前節(jié)點(diǎn)的右子樹(shù)，繼續(xù)下一輪遍歷
            root = root->right;
        }
        return result;    
    }
};

4.二叉樹(shù)的后序遍歷

給你一棵二叉樹(shù)的根節(jié)點(diǎn)?root?，返回其節(jié)點(diǎn)值的?后序遍歷?。

示例 1：

輸入：root = [1,null,2,3]
輸出：[3,2,1]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [1]
輸出：[1]

提示：

樹(shù)中節(jié)點(diǎn)的數(shù)目在范圍?[0, 100]?內(nèi)
-100 <= Node.val <= 100

解法參考：

/**
 * 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) {}
 * };
 */

/*方法
一：直接遞歸
二：可以發(fā)現(xiàn)后序遍歷其實(shí)是先序遍歷然后把中左右換成中右左，再顛倒過(guò)來(lái)，所以可以把先序遍歷換成中右左，然后再利用一個(gè)棧，訪問(wèn)操作先換成入棧，最后再去訪問(wèn)彈出這個(gè)棧
三：跟中序遍歷類(lèi)似，但是多加一個(gè)標(biāo)志位用來(lái)表示根節(jié)點(diǎn)的右節(jié)點(diǎn)是否已經(jīng)被訪問(wèn)過(guò)，如果已經(jīng)被訪問(wèn)過(guò)那么可以訪問(wèn)這個(gè)根節(jié)點(diǎn)，如果還沒(méi)訪問(wèn)過(guò)那就重新把根節(jié)點(diǎn)入棧，訪問(wèn)其右節(jié)點(diǎn)
*/

class Solution {
public:
        vector<int> postorderTraversal(TreeNode* root) 
        {
                vector<int> result;
                accessTree(result, root);
                return result;
        }
  
  //方法一遞歸，遞歸的話注意要傳引用進(jìn)去，否則對(duì)副本起作用后又消失了
        void accessTree(vector<int> &res, TreeNode* node)  
        {
                if(node == NULL) return;
                accessTree(res, node->left);
                accessTree(res, node->right);
                res.push_back(node->val);
        }
};

//方法三
/* vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> result;
        stack<TreeNode*> TreeStack;
        TreeNode* preroot = NULL;
        if(root == NULL )  return result;
        while(root != NULL || !(TreeStack.empty()) )
        {
            while(root != NULL)
            {
                TreeStack.push(root);
                root = root->left;
            }
/*彈出一個(gè)，當(dāng)其是否有右節(jié)點(diǎn)或右節(jié)點(diǎn)已經(jīng)訪問(wèn)過(guò)，則可以訪問(wèn)這個(gè)結(jié)點(diǎn)，注意訪問(wèn)完后要把preroot置為它，然后結(jié)點(diǎn)置為null；如果不滿足的話，則把這個(gè)結(jié)點(diǎn)壓棧，然后變成它的右節(jié)點(diǎn)，再次進(jìn)入上次的循環(huán)*/
/* 			root = TreeStack.top(); 
            TreeStack.pop();    
            if(root->right == NULL || root->right == preroot)
            {
               result.push_back(root->val);
               preroot = root ;
               root = NULL;     
            }else
            {
                TreeStack.push(root);
                root = root->right;
            }
        }
        return result;
    }
*/

5.二叉樹(shù)的最大深度

給定一個(gè)二叉樹(shù)?root?，返回其最大深度。

二叉樹(shù)的?最大深度?是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3

示例 2：

輸入：root = [1,null,2]
輸出：2

提示：

樹(shù)中節(jié)點(diǎn)的數(shù)量在?[0, 10⁴]?區(qū)間內(nèi)。
-100 <= Node.val <= 100

解法參考：

/**
 * 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) {}
 * };
 */
/*方法
一：直接遞歸來(lái)實(shí)現(xiàn)，每次往左和右遞歸然后取那個(gè)大的，最后加一
二：配合隊(duì)列來(lái)實(shí)現(xiàn)，每次進(jìn)隊(duì)列的是同一層的結(jié)點(diǎn)，每次處理完一批結(jié)點(diǎn)，讓深度加1
*/

//方法二
class Solution {
public:    
    int maxDepth(TreeNode* root)
    {
        int depth = 0;
        int size = 0;  //每次隊(duì)列中的個(gè)數(shù)，即該層節(jié)點(diǎn)數(shù)
        queue<TreeNode*> T;
        if(root == NULL) return 0;
        T.push(root);
        while(!T.empty())
        {
            size = T.size();
            while(size)
            {
            root = T.front();
            T.pop();
            if(root->left != NULL)
            {
                T.push(root->left);
            }
            if(root->right != NULL)
            {
                T.push(root->right);
            }            
            --size;    
            }
            ++depth;
        }
        return depth;
    }
        
};    
    
//方法一遞歸
/*    int maxDepth(TreeNode* root) 
    {
        if(root == NULL)  return 0;
        else return max(maxDepth(root->left),maxDepth(root->right))+1;    
    }
*/

6.對(duì)稱(chēng)二叉樹(shù)

給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn)?root?，檢查它是否軸對(duì)稱(chēng)。

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍?[1, 1000]?內(nèi)
-100 <= Node.val <= 100

解法參考：

/**
 * 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) {}
 * };
 */

/*方法
一：直接遞歸  遞歸地去比較左子樹(shù)的左節(jié)點(diǎn)與右子樹(shù)的右節(jié)點(diǎn)，左子樹(shù)的右節(jié)點(diǎn)跟右子樹(shù)的左節(jié)點(diǎn)
二：借助隊(duì)列來(lái)實(shí)現(xiàn)，每次雙雙進(jìn)出隊(duì)列，把整個(gè)跑完都是一樣的一對(duì)一對(duì)即為對(duì)稱(chēng)二叉樹(shù)
*/

//方法一
class Solution {
public:bool isSymmetric(TreeNode* root) 
            {
               if(root == NULL) return true;      
               return access(root->left,root->right); 
            }

        bool access(TreeNode* l,TreeNode* r)
        {
              if(l == NULL && r == NULL)  return true;  

              if(l == NULL || r == NULL)  return false;
              if(l->val != r->val) return false;

              return access(l->left,r->right) && access(l->right,r->left);  
        }

};

//方法二
/*class Solution {
public:bool isSymmetric(TreeNode* root) 
    {
        //從根節(jié)點(diǎn)的左右開(kāi)始
        TreeNode* u = root->left;
        TreeNode* v = root->right;
        //來(lái)個(gè)邊界判斷   不成立的話就開(kāi)始雙雙進(jìn)隊(duì)列了
        if(root == NULL || (u == NULL && v == NULL))  return true;
        queue<TreeNode*> T;
        T.push(u);
        T.push(v);

        while(!T.empty())    //循環(huán)的存放
        {
          u = T.front();
          T.pop();
          v = T.front();
          T.pop();
          /*判斷條件要注意判斷是否都為空，如果是返回跳出本次循環(huán) 再?gòu)梼蓚€(gè)出來(lái) 如果一半為空或者不相等則返回false 都不會(huì)則繼續(xù)進(jìn)隊(duì)列     全部循環(huán)結(jié)束返回真*/
/*          if( u == NULL && v == NULL) continue;   //注意不是用break          
          if( (u == NULL || v == NULL) || u->val != v->val )  return false;  

          T.push(u->left);
          T.push(v->right);

          T.push(u->right);
          T.push(v->left);            
        }
        return true;
    }
};
*/

7.平衡二叉樹(shù)

給定一個(gè)二叉樹(shù)，判斷它是否是平衡二叉樹(shù)

平衡二叉樹(shù)?是指該樹(shù)所有節(jié)點(diǎn)的左右子樹(shù)的深度相差不超過(guò) 1。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：true

示例 2：

輸入：root = [1,2,2,3,3,null,null,4,4]
輸出：false

示例 3：

輸入：root = []
輸出：true

提示：

樹(shù)中的節(jié)點(diǎn)數(shù)在范圍?[0, 5000]?內(nèi)
-10⁴ <= Node.val <= 10⁴

解法參考：

/**
 * 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) {}
 * };
 */


 /*方法
 一：自底向上遞歸解決，主要要想明白遞歸三要素，終止條件，處理過(guò)程，返回的值。 終止條件是root==null，處理過(guò)程是看高度差是否大于1，是的話返回負(fù)一。
二：自頂向下遞歸解決，好處是容易理解，壞處是重復(fù)調(diào)用，復(fù)雜度高 
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root == NULL) return true;
        else
        { return abs(depth(root->left)-depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        } 
    }
    
    int depth(TreeNode* root)
    {
        if(root == NULL) return 0;
        else return max(depth(root->left),depth(root->right))+1;    
    }

};

//自底向上遞歸
/*class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(root == NULL) return true;
        return helper(root) != -1;
    }

    int helper(TreeNode* root)
    {
        if(root == NULL) return 0;

        int left = helper(root->left);
        int right = helper(root->right);

        if( left == -1 || right == -1 || abs(left-right)>1 )
        {
            return -1;
        }
        return max(left,right)+1;
    }
};
*/

8.翻轉(zhuǎn)二叉樹(shù)

給你一棵二叉樹(shù)的根節(jié)點(diǎn)?root?，翻轉(zhuǎn)這棵二叉樹(shù)，并返回其根節(jié)點(diǎn)。

示例 1：

輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]

示例 2：

輸入：root = [2,1,3]
輸出：[2,3,1]

示例 3：

輸入：root = []
輸出：[]

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目范圍在?[0, 100]?內(nèi)
-100 <= Node.val <= 100

解法參考：

/**
 * 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) {}
 * };
 */

/*方法
一：最簡(jiǎn)單的就是直接遞歸
二：看到一種叫深度優(yōu)先的算法，利用一個(gè)棧，有點(diǎn)像是遍歷？然后每次處理?xiàng)?nèi)結(jié)點(diǎn)，處理過(guò)程是交換結(jié)點(diǎn)
*/ 

//方法二
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root == NULL) return root;
        stack<TreeNode*> T;
        TreeNode* result = root;
        T.push(root);
        int size = 0;
        while(!T.empty())
        {
            size = T.size();
            while(size)
            {
            root = T.top();
            T.pop();

            TreeNode* tmp = root->left;
            root->left = root->right;
            root->right = tmp;

            if(root->left != NULL)
            {
                T.push(root->left);
            }
            if(root->right != NULL)
            {
                T.push(root->right);
            }
            --size;
            }
        }
        return result;
    }
};

//直接遞歸
/*class Solution {
public:
    TreeNode* invertTree(TreeNode* root) 
    {
        if(root == NULL) return root;
        invertTree(root->left);
        invertTree(root->right);

        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};
*/

#23屆找工作求助陣地##二叉樹(shù)##筆面試##嵌入式##嵌入式軟件實(shí)習(xí)#

嵌入式軟件校招筆面試題匯總文章被收錄于專(zhuān)欄

該專(zhuān)欄是我整理的一些嵌入式軟件筆面試常見(jiàn)的題目，在有一定計(jì)算機(jī)基礎(chǔ)上，再過(guò)一遍該專(zhuān)欄的內(nèi)容，對(duì)應(yīng)屆生校招來(lái)說(shuō)基本上筆面試就沒(méi)什么問(wèn)題了！有任何疑問(wèn)可隨時(shí)與我聯(lián)系，一起交流一起進(jìn)步。