二叉树最小深度
minimum-depth-of-binary-tree
http://www.nowcoder.com/questionTerminal/e08819cfdeb34985a8de9c4e6562e724
注意递归的边界为“节点为叶节点”,否则就会过不了。
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int run(TreeNode* root) { // write code here // 后序遍历 if (root == nullptr){ return 0; } int minDepth = postOrder(root); return minDepth; } int postOrder(TreeNode* root){ // 注意判断是不是叶子节点 int leftDepth = 0; int rightDepth = 0; if(root->left == nullptr && root->right == nullptr){ return 1; } if(root->left != nullptr && root->right != nullptr){ leftDepth = postOrder(root->left) + 1; rightDepth = postOrder(root->right) + 1; return leftDepth > rightDepth ? rightDepth : leftDepth; } if(root->right != nullptr){ return postOrder(root->right) + 1; } return postOrder(root->left) + 1; } };
刷遍天下无敌手 文章被收录于专栏
秋招刷题历程