二叉树最大深度和最小深度_结点数为20的二叉树的最大深度为

二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。

如果二叉树为空，则深度为0
如果不为空，分别求左子树的深度和右子树的深度，去最大的再加1，因为根节点深度是1，要加进去。

int maxDepth(TreeNode *root) {
        // write your code (here)
        if(root == NULL)
            return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return leftDepth > rightDepth ? (leftDepth + 1) : (rightDepth + 1);
    }
1
2
3
4
5
6
7
8
9

二叉树的最小深度

给定一个二叉树，找出其最小深度。
二叉树的最小深度为根节点到最近叶子节点的距离。

刚开始拿到这道题，就想不是很简单吗，不就是最大深度的代码改为最小就行了吗？ 这样做的结果就是有些测试时通不过的。

因为如果出现斜树的情况，也就是说只有左子树，或只有右子树的时候，如果按照刚才说的那个算法来实现的话，得出的答案是0，明显是错误的。

两种实现方法，一种就是计算左子树和右子树深度的时候，判断是否等于0，如果等于0，说明该子树不存在，深度赋值为最大值。

第二种就是判断左子树或右子树是否为空，若左子树为空，则返回右子树的深度，反之返回左子树的深度，如果都不为空，则返回左子树和右子树深度的最小值

int minDepth(TreeNode *root) {
        // write your code here
        if(root == NULL)
            return false;
        if(root->left == NULL && root->right == NULL)
            return 1;

        int leftDepth = minDepth(root->left);
        if(leftDepth == 0)
            leftDepth = INT_MAX;

        int rightDepth = minDepth(root->right);
        if(rightDepth == 0)
            rightDepth = INT_MAX;

        return leftDepth < rightDepth ? (leftDepth + 1) : (rightDepth + 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int minDepth(TreeNode *root) {
        // write your code here
        if(root == NULL)
            return false;

        if(root->left == NULL) return minDepth(root->right) + 1;
        if(root->right == NULL) return minDepth(root->left) + 1;

        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);

        return leftDepth < rightDepth ? (leftDepth + 1) : (rightDepth + 1);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

(97) Maximum Depth of Binary Tree
http://www.lintcode.com/zh-cn/problem/maximum-depth-of-binary-tree/
(155) Minimum Depth of Binary Tree
http://www.lintcode.com/zh-cn/problem/minimum-depth-of-binary-tree/