题面
找出二叉树的最小深度(从根节点到某个叶子节点路径上的节点个数最小)。
算法
算法参照二叉树的最大深度,这里需要注意的是当某节点的左右孩子都存在时,就返回左右子树的最小深度;如果不都存在,就需要返回左右子树的最大深度(因为子节点不存在的话,通向该子树的路径就走不同,就不存在深度,也无法比较。只能从另一子树方向走。)如果左右孩子不都存在时还取小值,那返回的就是父节点的深度,会出错。
源码
1 class Solution { 2 public: 3 int minDepth(TreeNode* root) { 4 if(root == nullptr) 5 return 0; 6 if(root->left && root->right) 7 return min(getDepth(root->left, 1), getDepth(root->right, 1)); 8 else 9 return max(getDepth(root->left, 1), getDepth(root->right, 1)); 10 } 11 12 int getDepth(TreeNode* p, int deep) 13 { 14 if(p == nullptr) 15 return deep; 16 if(p->left && p->right) 17 return min(getDepth(p->left, deep+1), getDepth(p->right, deep+1)); 18 else 19 return max(getDepth(p->left, deep+1), getDepth(p->right, deep+1)); 20 } 21 };