111. 二叉树的最小深度
这道题相比 104. 二叉树的最大深度 还是难上一些的,但也不算太难。
BFS
/** * 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*> qqq;; qqq.push(root); int depth=0; while(!qqq.empty()) { depth++; int size=qqq.size(); for(int i=0;i<size;i++) { TreeNode *t=qqq.front(); qqq.pop(); if(!t->left&&!t->right) return depth; if(t->left) qqq.push(t->left); if(t->right) qqq.push(t->right); } } return depth; } };
DFS
/** * 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==nullptr&&root->right==nullptr) return 1; if(!root->left||!root->right) return minDepth(root->left)+minDepth(root->right)+1; /* if(root->left&&root->right==nullptr) return minDepth(root->left)+1; if(root->right&&root->left==nullptr) return minDepth(root->right)+1; */ return min(minDepth(root->left),minDepth(root->right))+1; } };
标签:right,TreeNode,int,leetcode111,nullptr,最小,二叉树,root,left From: https://www.cnblogs.com/uacs2024/p/16847406.html