easy 二叉樹的最小深度 深度優先搜尋 遞歸 廣度優先搜尋 隊列 疊代

深度優先搜尋 疊代：

不能碰到 null節點 就傳回，null節點 的左右節點可能 非null

c++

/**
 * 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:
    int minDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        }
        if(root->left && root->right){  // 左右樹都不為空
            return min(minDepth(root->left), minDepth(root->right)) + 1;
        }

        // 左右樹有一個為空，傳回不為空的樹(max)深度+1
        // 左右樹都為空(深度為0)，傳回0+1
        return max(minDepth(root->left), minDepth(root->right)) + 1;
    }
};

           

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

           

廣度優先搜尋 隊列 疊代：

層序周遊

c++

/**
 * 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:
    int minDepth(TreeNode* root) {
        if (root==nullptr){
            return 0;
        }
        queue<TreeNode*> que;
        que.push(root);
        int d = 0;
        while(!que.empty()){
            d++;  // root 不為空，層數+1
            int n = que.size();  //  記錄每一層元素個數
            while(n){
                TreeNode* node = que.front();
                que.pop();
                if (node->left){
                    que.push(node->left);
                }
                if (node->right){
                    que.push(node->right);
                }
                if (!node->left && !node->right){  // 左右樹都為空
                    return d;
                }
                n--;  // 該層元素-1
            }
        }

        return d;
    }
};

           

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        q = collections.deque([root])   # 建立python雙端隊列，并放入p
        h = 0
        while q:

            h +=1
            n = len(q)  # 這一層中元素的個數
            while n:
                node = q.popleft()  # 傳回并删除隊列頂端元素
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                if not node.left and not node.right:
                    return h

                n -= 1 # 這一層中元素的個數-1

            # h +=1  # 不能在此處才處理h

        return h