leetcode 111. Minimum Depth of Binary Tree DFS深度优先遍历 + 添加对叶子节点判断

不念不忘少年蓝@ 2022-06-08 03:16 99阅读 0赞

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.

本题考查的就是平衡二叉树的最小深度，其实跟Maximum Depth of Binary Tree非常类似，只是这道题因为是判断最小深度，所以必须增加一个叶子的判断（因为如果一个节点如果只有左子树或者右子树，我们不能取它左右子树中小的作为深度，因为那样会是0，我们只有在叶子节点才能判断深度，而在求最大深度的时候，因为一定会取大的那个，所以不会有这个问题）。这道题同样是递归和非递归的解法，递归解法比较常规的思路，比Maximum Depth of Binary Tree多加一个左右子树的判断。

代码如下：

/*class TreeNode
    {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }*/
    
    public class Solution 
    {
        /*
         * 这道题是树的题目，其实跟Maximum Depth of Binary Tree非常类似，只是这道题因为是判断最小深度，
         * 所以必须增加一个叶子的判断（因为如果一个节点如果只有左子树或者右子树，我们不能取它左右子树中
         * 小的作为深度，因为那样会是0，我们只有在叶子节点才能判断深度，而在求最大深度的时候，因为一定会
         * 取大的那个，所以不会有这个问题）。这道题同样是递归和非递归的解法，递归解法比较常规的思路，
         * 比Maximum Depth of Binary Tree多加一个左右子树的判断，代码如下：
         */
        public int minDepth(TreeNode root)
        {
            if(root==null)
                return 0;
            else
                return getMinDepth(root);
        }
    
        int getMinDepth(TreeNode root) 
        {
            if(root==null)
                return 0;
            else
            {
                if(root.left==null)
                    return getMinDepth(root.right)+1;
                if(root.right==null)
                    return getMinDepth(root.left)+1;
                int left=getMinDepth(root.left)+1;
                int right=getMinDepth(root.right)+1;
                return Math.min(left, right);
            }
        }
    }

下面是C++的做法，这里要注意的是，由于我们是判断最小高度的，所以**一定要添加对叶子节点为null的判断**，这个和之前的题不太一样。

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <algorithm>
    
    using namespace std;
    
    /*
    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 == NULL)
                return 0;
            else
            {
                if (root->left == NULL)
                    return minDepth(root->right) + 1;
                else if (root->right == NULL)
                    return minDepth(root->left) + 1;
                else 
                {
                    int left = minDepth(root->right) + 1;
                    int right = minDepth(root->left) + 1;
                    return min(left,right);
                }
            }
        }
    };