二叉树最小深度

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;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务