二叉树的最小深度

Question

我正在阅读二叉树。在练习编码问题时，我遇到了一些要求查找二叉树深度的解决方案。 现在按照我的理解深度不从根边缘节点（叶节点中的叶节点/二进制树的情况）的

什么是二叉树{1,2}

作为每最小深度我的解决方案应该是1.

Answer 1

二叉树的minDepth意味着从根到叶节点的最短距离。虽然你的二叉树的minDepth是1还是2是有争议的，这取决于你是否想要到一个空节点的最短距离，在这种情况下，答案将是1或者到同胞也是一个空节点的最短距离空节点，在这种情况下，答案二叉树{1,2}将2.一般来说，前者被要求，并在Cracking the Coding Interview提到的算法下面，我们作为

int minDepth(TreeNode root) { 
    if (root == null) { return 0;} 
     return 1 + Math.min(minDepth(root.left), minDepth(root.right)); 
} 

Answer 2

记住叶解节点既没有离开也没有正确的孩子。

1 
/
/
2 

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

#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

二叉树的深度是从根到叶的最长路径的长度。在我看来，深度应该是2.

Answer 4

鉴于路径的深度是沿着此路径从根节点到叶节点的节点数。最小值是从根节点到LEAF节点的节点数最少的路径。在这种情况下，唯一的叶节点是2（A叶节点被定义为没有子节点的节点）因此，唯一的深度，并且还分钟深度是2

Java中的示例代码：

public class Solution { 
    public int minDepth(TreeNode root) { 
     if (root==null) return 0; 
     if ((root.left==null) || (root.right==null)) { 
      return 1+Math.max(minDepth(root.left),minDepth(root.right)); 
     } 
     return 1+Math.min(minDepth(root.left),minDepth(root.right)); 
    } 
} 

Answer 5

我测试的解决方案

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)); 
} 

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

'else if'分支的相似逻辑。在'return'语句中，'if'条件失败，我们返回1（当前节点）+递归调用的最小值给左右分支。

Answer 6

public int minDepth(TreeNode root){ 
     if(root==null) 
      return 0; 
     else if(root.left==null && root.right==null) 
      return 1; 
     else if(root.left==null) 
      return 1+minDepth(root.right); 
     else if(root.right==null) 
      return 1+minDepth(root.left); 
     else 
     return 1+Math.min(minDepth(root.right), minDepth(root.left)); 
    } 

Answer 7

根节点将具有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; 
}