二叉樹的最小深度

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