讨论/《深度优先搜索》 - 练习:二叉树的最小深度/
《深度优先搜索》 - 练习:二叉树的最小深度
共 7 个回复

BFS....

class Solution {
public:
    int minDepth(TreeNode* root) {
        int ans = 0;
        queue<TreeNode*> rootQue;
        if(root){
            ans = 1;
            rootQue.push(root);
        }
        while(!rootQue.empty()){
            int size = rootQue.size();
            for(int i = 0; i < size; i++){
                TreeNode* cur = rootQue.front();
                rootQue.pop();
                if(cur->left)   rootQue.push(cur->left);
                if(cur->right)   rootQue.push(cur->right);
                if((!cur->right) && (!cur->left))   return ans++;
            }
            ans++;
        }
        return ans;
    }
};
2
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
        {
            return 0;
        }
        int leftInfo = minDepth(root->left);
        int rightInfo = minDepth(root->right);
        return (leftInfo==0 || rightInfo==0) ? leftInfo + rightInfo + 1 : min(leftInfo,rightInfo) + 1;
    }
};
2
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        } else if (root.left == null) {
            return minDepth(root.right) + 1;
        } else if (root.right == null) {
            return minDepth(root.left) + 1;
        } else {
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            return leftDepth > rightDepth ? rightDepth + 1 : leftDepth + 1;
        }
    }
}

BFS:

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 若根节点不存在,返回0
        if not root:
            return 0
        
        count = 0
        queue = deque([root])
        
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                # 若为叶子节点,返回当前count+1(因为没有添加进队列所以要加上自身)
                if not node.left and not node.right:
                    return count + 1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            count += 1

        return count 

好想用BFS,但是还是要练习DFS

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        if not root.left and not root.right:
            return 1
        min_left = self.minDepth(root.left)
        min_right = self.minDepth(root.right)
        if min_left and min_right:
            return 1 + min(min_left, min_right)
        return 1 + min_left if min_left else 1 + min_right
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) return 1 + left + right;
        return 1 + Math.min(left, right);
    }
}
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root : return 0
        lH = self.minDepth(root.left)
        rH = self.minDepth(root.right)
        if not lH : return rH + 1
        if not rH : return lH + 1
        return min(lH,rH) + 1