week2-#111-Easy & #104-Easy

104原题地址：https://leetcode.com/problems/maximum-depth-of-binary-tree/description/

111原题地址：https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

题目描述

把这两题放一起因为是因为这两题要求差不多，104题要求一棵二叉树的最大深度，111题要求一棵二叉树的最小深度。

104题思路

用DFS遍历，每个DFS返回自己的两个子节点的路径长度中较大的那一个。
代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int DFS(TreeNode* root,int current_depth){
        if(root==NULL){
            return current_depth;
        }
        current_depth+=1;
        int depth1 = DFS(root->left,current_depth);
        int depth2 = DFS(root->right,current_depth);
        return (depth1>depth2?depth1:depth2);
    }
    
    int maxDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int depth = 0;
        return DFS(root,depth);
    }
};

111题思路

111题求最小深度要比104麻烦一些，因为在DFS里不能直接返回两个子节点的路径长度里较小的那个，否则遇到一些节点的某个子节点为空就会直接返回到这个节点为止的路径长度。如下图

如果直接返回子节点路径长度里较小的那个，这个样例里的返回值为2而不是3。所以这一题要根据子节点的具体情况来决定进行什么样的操作。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int DFS(TreeNode* root,int current_depth){
        current_depth+=1;
        if(root->left!=NULL && root->right!=NULL){
            int left =DFS(root->left,current_depth);
            int right = DFS(root->right,current_depth);
            return (left>right?right:left);
        }
        if(root->left == NULL && root->right ==NULL){
            return current_depth;
        }
        if(root->left!=NULL){
            return DFS(root->left,current_depth);
        }
        if(root->right !=NULL ){
            return DFS(root->right,current_depth);
        }
    }
    
    int minDepth(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int depth = 0;
        return DFS(root,depth);
    }
};