二叉树的最小深度

Question

我正在读二叉树。在练习编码问题时，我遇到了一些解决方案，其中要求找到二叉树的最小深度。现在根据我的理解，深度是从根到节点的边数（叶节点的情况下为叶节点/二叉树）

二叉树{1,2}的最小深度是多少

根据我的解决方案，应该是1。

Answer 1

根节点的深度为0，所以这里给定树的深度为1，请参考下面的递归和迭代解，以找到二叉树的最小深度。

递归解：

public static int findMinDepth(BTNode root) {
    if (root == null || (root.getLeft() == null && root.getRight() == null)) {
        return 0;
    }
    int ldepth = findMinDepth(root.getLeft());
    int rdepth = findMinDepth(root.getRight());

    return (Math.min(rdepth + 1, ldepth + 1));
}

迭代解决方案：

public static int minDepth(BTNode root) {
    int minDepth = Integer.MAX_VALUE;
    Stack<BTNode> nodes = new Stack<>();
    Stack<BTNode> path = new Stack<>();
    if (root == null) {
        return -1;
    }
    nodes.push(root);
    while (!nodes.empty()) {
        BTNode node = nodes.peek();
        if (!path.empty() && node == path.peek()) {
            if (node.getLeft() == null && node.getRight() == null && path.size() <= minDepth) {
                minDepth = path.size() - 1;
            }
            path.pop();
            nodes.pop();
        } else {
            path.push(node);
            if (node.getRight() != null) {
                nodes.push(node.getRight());
            }
            if (node.getLeft() != null) {
                nodes.push(node.getLeft());
            }
        }
    }
    return minDepth;
}

Answer 2

请记住，叶节点既没有左子节点，也没有右子节点。

  1
  /
 /
2

这里2是叶节点，但1不是。所以这种情况下的最小深度是2，假设根节点的深度是1。

#include<vector>
#include<iostream>
#include<climits>
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;
        return getDepth(root);
    }
    int getDepth(TreeNode *r ){
        if(r == NULL) return INT_MAX;
        if(r->left == NULL && r->right == NULL)
            return 1;
        return 1+ min(getDepth(r->left), getDepth(r->right));
    }
};

Answer 3

我的测试解决方案

public int minDepth(TreeNode root) {
    if(root == null){
        return 0;
    }
    int ldepth = minDepth(root.left);
    int rdepth = minDepth(root.right);
    if(ldepth == 0){
        return 1+rdepth;
    }else if(rdepth == 0){
        return 1+ldepth;
    }

    return (1 + Math.min(rdepth, ldepth));
}

在这里，我们计算节点的深度（最小左子树深度）和深度（最小右子树深度）。然后，如果深度为零，但深度不是，这意味着当前节点不是叶节点，因此返回1深度。当我们为当前叶节点返回1 0的时候，如果r深度和l深度都是0，那么'if'条件仍然有效。

“else-if”分支的类似逻辑。在“return”语句中，当两个“if”条件都失败时，我们将向左分支和右分支返回递归调用的最小值1（当前节点）。