代碼隨想錄算法訓練營|第十六天|104.二叉树的最大深度 、111.二叉树的最小深度 、222.完全二叉树的节点个数。刷题心得（c++）

发布于：2023-09-22 ⋅ 阅读:(82) ⋅ 点赞:(0)

目录

讀題

104.二叉树的最大深度

自己看到题目的第一想法

111.二叉树的最小深度

自己看到题目的第一想法

看完代码随想录之后的想法

222.完全二叉树的节点个数

自己看到题目的第一想法

104.二叉树的最大深度  - 實作

遞迴思路

錯誤思路

正確思路

迭代思路

遞迴代碼

錯誤代碼

正確代碼

迭代代碼

111.二叉树的最小深度  - 實作

遞迴思路

錯誤思路

正確思路

迭代思路

錯誤思路

正確思路

遞迴代碼

錯誤代碼

正確代碼

迭代代碼

222.完全二叉树的节点个数 - 實作

思路

遞迴思路

迭代思路

Code

遞迴代碼

迭代代碼

讀題

104.二叉树的最大深度

自己看到题目的第一想法

這道題目昨天用層序遍歷的時候有做過，在想法上就是迭代到最後一層的時候返回的不是數組，而是當下的深度，深度則可以在每一次遞迴的時候depth + 1 ，就可以求到了。

111.二叉树的最小深度

自己看到题目的第一想法

這道題目昨天用層序遍歷的時候有做過，在想法上就是只要遇到一個節點的左右子樹都為空時，直接回傳當下的深度，因為這時就在這棵樹的最小深度了。

看完代码随想录之后的想法

在實作遞迴的時候反而卡住了，看完之後才知道我應該要對左右子樹其中一個為空的狀況進行判斷，不能直接使用min，看完之後對於題目的定義比較清晰

222.完全二叉树的节点个数

自己看到题目的第一想法

看到題目，想到之前有講到的完全二叉樹與滿二叉樹的差別，完全二叉樹是只要非葉子節點，那數量一定是滿的，如果是葉子節點的話就要由左到右，中間不能為空，

其實整體跟深度很像，只是深度是在第一個回圈++，個數則是在第二個回圈就要++

迭代跟遞迴的作法基本上跟最大深度的做法沒有差太多

104.二叉树的最大深度  - 實作

遞迴思路

錯誤思路

  1. 傳入的參數值
    1. root → 從根結點開始遞迴，之後到每個節點
    2. depth 深度值
  2. 終止條件
    1. if (root == null)
  3. 單遞迴條件
    1. if(root→right) treveral(root→right, depth+1);
    2. if(root→left)treveral(root→left, depth+1

錯誤點: 這不是迭代，並且左右子樹的深度有可能不一樣，所以應該是要分為左右子樹分別去底下找最後比較大小，另外傳入值只需要cur，因為return 就是depth值

正確思路

  1. 傳入的參數值
    1. root → 從根結點開始遞迴，之後到每個節點
  2. 終止條件
    1. if (root == null) return 0 —> 因為是int，須返回整數值
  3. 單遞迴條件
    1. int leftdepth = findMaxDepth(cur→left);
    2. int rightdepth = findMaxDepth(cur→right);
    3. int depth = 1 + max(leftdepth, rightdepth);
    4. return depth

錯誤點: 這不是迭代，並且左右子樹的深度有可能不一樣，所以應該是要分為左右子樹分別去底下找最後比較大小，另外傳入值只需要cur，因為return 就是depth值

迭代思路

  1. 設置一個queue來暫存每一層的元素
  2. 設定depth = 0; → 紀錄深度
  3. 進入回圈

    1. 假設queue不為空 → 代表目前仍有節點

    2. 設置size = que.size() -> 代表每層的個數

    3. 設立一個回圈size--

      1. 使用建立一個節點暫存node
      2. 將queue的元素pop出來
      3. 將暫存的左右子樹假設不為空則加入到queue當中

      <aside> 💡 為甚麼不是直接que.size()-- 是因為que.size會一直變動，而size其實所存的只有每一層的個數，所以每次回圈的size都會是該層的元素個數

      </aside>

遞迴代碼

錯誤代碼

class Solution {
public:
    int findMaxDepth(TreeNode* cur, int depth) {
        if(cur == NULL) return depth; 
        if(cur->left) findMaxDepth(cur->right, depth+1);
        if(cur->right) findMaxDepth(cur->left, depth+1);
        return depth;
    }
    int maxDepth(TreeNode* root) {
        int depth = 0;
        findMaxDepth(root, depth);
        return depth;
    }
};

正確代碼

class Solution {
public:
    int findMaxDepth(TreeNode* cur) {
        if(cur == NULL) return 0 ; 
        int leftdepth = findMaxDepth(cur->left); 
        int rightdepth = findMaxDepth(cur->right);
        int depth = 1 + max(leftdepth, rightdepth);
        return depth;
    }
    int maxDepth(TreeNode* root) {
        int depth = findMaxDepth(root);;
        return depth;
    }
};

迭代代碼

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        int depth = 0;
    
        while(!que.empty()) {
            int size = que.size();
            while(size--) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

 

111.二叉树的最小深度  - 實作

遞迴思路

錯誤思路

  1. 傳入的參數值
    1. root → 從根結點開始遞迴，之後到每個節點
    2. depth → 因為要記錄目前走到哪一層
  2. 終止條件
    1. if (root == null) return 0 —> 因為是int，須返回整數值
    2. if(!node→right && !node→left) return depth;
  3. 單遞迴條件
    1. leftdepth = findMinDepth(cur->left, depth + 1);
    2. rightdepth = findMinDepth(cur->right, depth + 1);
    3. return 1 + min(leftdepth, rightdepth); → 1 代表第一層

錯誤點: 這是要求根結點到葉節點的最小距離，所以需要去判斷左右子樹是否為空，如果都不為空我才去抓左右子樹的最小節點。

正確思路

  1. 傳入的參數值
    1. root → 從根結點開始遞迴，之後到每個節點
  2. 終止條件
    1. if (root == null) return 0 —> 因為是int，須返回整數值
  3. 單遞迴條件
    1. leftdepth = findMinDepth(cur->left);
    2. rightdepth = findMinDepth(cur->right);
    3. if(cur→left && !cur→right) return 1 + rightdepth;
    4. if(!cur→left && cur→right) return 1 + leftdepth;
    5. return 1 + min(leftdepth, rightdepth); → 1 代表第一層
    6. return depth

錯誤點: 這是要求根結點到葉節點的最小距離，所以需要去判斷左右子樹是否為空，如果都不為空我才去抓左右子樹的最小節點。

迭代思路

錯誤思路

  1. 設置一個queue來暫存每一層的元素
  2. 設定depth = 0; → 紀錄深度
  3. 進入回圈

    1. 假設queue不為空 → 代表目前仍有節點

    2. 設置size = que.size() -> 代表每層的個數

    3. 設立一個回圈size--

      1. 使用建立一個節點暫存node
      2. 將queue的元素pop出來
      3. 假設某一個節點左右子樹都為空，則直接return 該層深度
      4. 將暫存的左右子樹假設不為空則加入到queue當中

    4. 跳出後depth++

      <aside> 💡 為甚麼不是直接que.size()-- 是因為que.size會一直變動，而size其實所存的只有每一層的個數，所以每次回圈的size都會是該層的元素個數

      </aside>

錯誤點: 應該在假設不為空的時候就直接depth++，因為在最大深度這樣做沒有關係，但是假設在最小深度，要馬return 時要加一，要馬調換順序

正確思路

  1. 設置一個queue來暫存每一層的元素
  2. 設定depth = 0; → 紀錄深度
  3. 進入回圈
    1. 假設queue不為空 → 代表目前仍有節點
    2. Depth++
    3. 設置size = que.size() -> 代表每層的個數
    4. 設立一個回圈size--
      1. 使用建立一個節點暫存node
      2. 將queue的元素pop出來
      3. 假設某一個節點左右子樹都為空，則直接return 該層深度
      4. 將暫存的左右子樹假設不為空則加入到queue當中

遞迴代碼

錯誤代碼

class Solution {
public:
    int findMinDepth(TreeNode* cur, int depth) {
        if(cur == NULL) return 0 ; 
        if(!cur->left && !cur->right) return depth;
        int leftdepth = findMinDepth(cur->left, depth + 1); 
        int rightdepth = findMinDepth(cur->right, depth + 1);
        return 1 + min(leftdepth, rightdepth);
    }
    int minDepth(TreeNode* root) {
        int depth = findMinDepth(root, 0);
        return depth;
    }
};

正確代碼

class Solution {
public:
    int findMinDepth(TreeNode* cur) {
        if(cur == NULL) return 0 ; 
        int leftdepth = findMinDepth(cur->left); 
        int rightdepth = findMinDepth(cur->right);
        if(!cur->left && cur->right)return 1 + rightdepth;
        if(cur->left && !cur->right)return 1 + leftdepth;
        return 1 + min(leftdepth, rightdepth);

    }
    int minDepth(TreeNode* root) {
        return findMinDepth(root);
    }
};

迭代代碼

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        int depth = 0;
   
        while(!que.empty()) {
            int size = que.size();
            while(size--) {
                TreeNode* node = que.front();
                que.pop();
                if(!node->left && !node->right) return depth;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

 

222.完全二叉树的节点个数 - 實作

思路

遞迴思路

  1. 傳入值 root ，回傳int
  2. 終止條件: root == NULL , return 0 ;
  3. 遞迴
    1. 記錄左子樹的count
    2. 紀錄右子樹的count
    3. 最後return 1 + 左count + 右 count

迭代思路

  1. 建立一個queue來儲存暫時元素
  2. 建立一個count紀錄目前元素數量
  3. while回圈條件當!que.empty()
    1. 建立一個size = que.size()記錄每一層數量
    2. while回圈 size--
      1. 暫時節點儲存que.front()
      2. que.pop();
      3. 左右節點加入到que
      4. count++;
  4. return count;

Code

遞迴代碼

class Solution {
public:
    int getNodesCount(TreeNode* cur) {
        if(cur == NULL) return 0;
        int leftcount = getNodesCount(cur->left);
        int rightcount = getNodesCount(cur->right);
        return 1 + leftcount + rightcount;
    }
    int countNodes(TreeNode* root) {
        return getNodesCount(root);
    }
};

迭代代碼

class Solution {
public:
    int countNodes(TreeNode* root) {
        queue<TreeNode*> que;
        int count = 0;
        if(root != NULL) que.push(root);
        while(!que.empty()) {
            int size = que.size();
            while(size--) {
                TreeNode* node = que.front();
                que.pop();
                if(node->left)que.push(node->left);
                if(node->right)que.push(node->right);
                count++;
            }
        }
        return count;
    }
};

 

總結

自己实现过程中遇到哪些困难

今天卡住我的反而是在遞迴，對於傳入值以及單遞迴的思考不足，自己需要再對遞迴的部分進行了解

而在迭代上反而比較清晰，腦袋中有那個畫面存在，對於目前的我來說感覺迭代更加直觀一點

今日收获，记录一下自己的学习时长

今天因為有兩題昨天做過，所以整體大概花不到兩個小時就把題目做完了，但每天這樣做遞迴的題目，感覺自己對於二叉樹又有更深一點的理解了。

相關資料

详细布置

104.二叉树的最大深度

题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.二叉树的最大深度.html

111.二叉树的最小深度

题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.二叉树的最小深度.html

222.完全二叉树的节点个数

题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.完全二叉树的节点个数.html

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布