leetcode演算法之遍歷(BFS與DFS)

今天來盤一盤 **遍歷 ** 這類題目

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

遍歷

層次遍歷（BFS）

  • 102 二叉樹的層序遍歷(medium)
  • 637 二叉樹的層平均值 (Easy)
  • 513 找樹左下角的值 (medium)

深度優先遍歷（DFS）

  • 144 二叉樹的前序遍歷 (meidum)
  • 145 二叉樹的後序遍歷 (hard)
  • 94 二叉樹的中序遍歷 (Medium)

BFS

寬度優先遍歷（BFS）採用隊列的方式，依次遍歷一棵樹。

基本的套路程式碼，就是102題目中的程式碼思路。

102 二叉樹的層序遍歷(medium)

  • 題解 BFS
    • 使用隊列存儲當前節點的指針以及當前節點的層次
    • 循環遍歷隊列中的元素
    • 對於一個隊首節點，如果其左子節點存在就將左子節點入隊，如果右子節點存在，將右子節點入隊列
    • 按照隊首節點的層次數，將節點的值插入vector中對於的位置。
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (root == nullptr) return {};
        // 使用隊列存儲節點與節點所對應的層次
        queue<pair<TreeNode*, int>> nodeQ;
        vector<vector<int>> res;
        // 將根節點以及對應的層次0，入隊
        nodeQ.push(make_pair(root, 0));
        // 如果隊列不為空，就一直遍歷隊列元素
        while (!nodeQ.empty()){
            // 拿出隊首的節點指針以及層次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 隊首元素出隊

            if (res.size() <= level){
                res.push_back({});
            }
            res[level].push_back(nodePoint->val);

            // 如果左子樹存在，就將左子節點入隊
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子樹存在，就將右子節點入隊
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        return res;  
    }
};

637 二叉樹的層平均值 (Easy)

與上一題一致

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        if (! root) return {};
        vector<double> nodesum;
        vector<int> cnt;
        queue<pair<TreeNode*, int>> nodeQ;
        nodeQ.push(make_pair(root, 0)); 
        while (!nodeQ.empty()){
            // 拿出隊首的節點指針以及層次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 隊首元素出隊
            if (nodesum.size() <= level){
                nodesum.push_back(nodePoint->val);
                cnt.push_back(1);
            }
            else{
                nodesum[level] += nodePoint->val;
                cnt[level]++;
            }

            // 如果左子樹存在，就將左子節點入隊
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子樹存在，就將右子節點入隊
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        for (int i = 0; i< nodesum.size(); i++){
            nodesum[i] /= cnt[i];
        }
        return nodesum;
    }
};

513 找樹左下角的值 (medium)

  • 題解： 最左邊的值，就是採用層次遍歷保存每層開始的第一個值
    • 同樣的層次遍歷方法。
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if (root == nullptr) return {};

        // 使用隊列存儲節點與節點所對應的層次
        queue<pair<TreeNode*, int>> nodeQ;
        // pair的第一個參數為每層的第一個節點值，第二個參數為層次
        pair<int, int> res(0, -1);
        // 將根節點以及對應的層次0，入隊
        nodeQ.push(make_pair(root, 0));
        // 如果隊列不為空，就一直遍歷隊列元素
        while (!nodeQ.empty()){
            // 拿出隊首的節點指針以及層次
            auto nodeLevel = nodeQ.front();
            auto nodePoint = nodeLevel.first;
            int level = nodeLevel.second;
            nodeQ.pop();  // 隊首元素出隊

            // 如果開始了一個新的層次，將在這一層最左側的元素保存。
            if (level > res.second){
                res.first = nodePoint->val;
                res.second = level;
            }

            // 如果左子樹存在，就將左子節點入隊
            if (nodePoint->left){
                nodeQ.push(make_pair(nodePoint->left, level+1));
            }
            // 如果右子樹存在，就將右子節點入隊
            if (nodePoint->right){
                nodeQ.push(make_pair(nodePoint->right, level+1));
            }
        }
        return res.first;  
    }
};

DFS

深度優先遍歷（DFS）就是遞歸訪問一棵樹。

144 二叉樹的前序遍歷 (meidum)

前序遍歷： 根——左——右

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root, res);
        return res;
    }
    void preorder(TreeNode* root, vector<int>& res){
        if (root == nullptr) return;
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
};

145 二叉樹的後序遍歷 (hard)

後序遍歷： 左——右——根

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode* root, vector<int>& res){
        if (root == nullptr) return;
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
};

94 二叉樹的中序遍歷 (Medium)

中序遍歷： 左——根——右

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
    void inorder(TreeNode* root, vector<int> & res){
        if (root == nullptr) return ;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
};

更多分類刷題資料

Tags:

VirMach 便宜 VPS