leetcode Depth of binary tree

题目链接

• 二叉树的最大深度maximum-depth-of-binary-tree

• 二叉树的最小深度minimum-depth-of-binary-tree

题目描述(Description)

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

二叉树的最大深度

给一个二叉树，找到它的最大深度。

最大深度是沿着根节点带最远叶节点路径经过的所有结点数量。

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

二叉树的最小深度

给一个二叉树，找到它的最小深度。
最小深度是沿着根节点到最近叶节点的路径经过的所有结点数量。

分析(Analysis)

最大深度

• 递归真是好东西。分别递归左右子树，然后取二者最大值+1根节点返回。

• 根节点为空，返回0。

最小深度

• 与最大深度略微不同。要考虑到只有左子树或只有右子树的情况。

• 根节点为空，返回0；

• 没有左子树，右子树的长度+1就是最小深度。

• 没有右子树，左子树的长度+1就是最小深度。

代码(Code)

二叉树的最大深度

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(!root)
            return 0;
        int maxLeft=maxDepth(root->left);
        int maxRight=maxDepth(root->right);
        return max(maxLeft,maxRight)+1;
    }
};



**二叉树的最小深度**


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if(!root)
            return 0;
        int minLeft=minDepth(root->left);
        int minRight=minDepth(root->right);
        if(minLeft==0&&minRight!=0)
            minLeft=INT_MAX;//若左子树为空，左子树最小深度设为最大值
        if(minRight==0&&minLeft!=0)
            minRight=INT_MAX;//若左子树为空，左子树最小深度设为最大值
        return min(minLeft,minRight)+1;
    }
};