# C#LeetCode刷题之#111-二叉树的最小深度​​​​​​​（Minimum Depth of Binary Tree）

3
/ \
9  20
/      \
15       7

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.

Note: A leaf is a node with no children.

Given binary tree [3,9,20,null,null,15,7],

3
/ \
9  20
/      \
15      7
return its minimum depth = 2.

```public class Program {

public static void Main(string[] args) {
var root = new TreeNode(1) {
left = new TreeNode(2),
right = new TreeNode(3)
};

var res = IsBalanced(root);
Console.WriteLine(res);

root = new TreeNode(1) {
left = new TreeNode(2) {
left = new TreeNode(3) {
left = new TreeNode(4)
}
},
right = new TreeNode(5) {
right = new TreeNode(6)
}
};

res = IsBalanced2(root);
Console.WriteLine(res);

}

public static bool IsBalanced(TreeNode root) {
//传统递归法，简单易写
//空树是平衡二叉树，因为左右子树数量都是 0
if(root == null) return true;
//左右子树高度差大于 1，不是平衡二叉树
if(Math.Abs(MaxDepth(root.left) - MaxDepth(root.right)) > 1) return false;
//判定左右子树是否为平衡二叉树
return IsBalanced(root.left) && IsBalanced(root.right);
}

public static int MaxDepth(TreeNode root) {
//计算树每个子树的高度
if(root == null) return 0;
var left = MaxDepth(root.left);
var right = MaxDepth(root.right);
return Math.Max(left, right) + 1;
}

public static bool IsBalanced2(TreeNode root) {
//优化递归法
//此段代码引用自 LeetCode 的提交代码
//由本人添加注释
return MaxDepth2(root) >= 0;
}

public static int MaxDepth2(TreeNode root) {
//如果是空树，判定为平衡的
if(root == null) return 0;
//计算左右子树的高度
var left = MaxDepth2(root.left);
var right = MaxDepth2(root.right);
//如果左子树、右子树或高度差大于 1，则返回 -1
//-1 表示判定为非平衡树，立即返回
//导致调用堆栈在回溯时发现上一次是 -1
//由于代码 left < 0 || right < 0 的存在，会使 -1 逐步上传
//又被回溯到上上一次，一直到无法回溯时为止
//按照原代码作者的部分注释，即不平衡的树会被传染到最上层
//也即当发现一个 -1 时，该代码以非常高的效率判定原树为非平衡的
//因为当前树为平衡的，不能判定原树是不是平衡的
//但当前树为非平衡的，原树肯定是不平衡的
//感谢原作者的代码为我们分享如此巧妙的优化
if(left < 0 || right < 0 || Math.Abs(left - right) > 1) return -1;
return Math.Max(left, right) + 1;
}

public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}

}```

```2
4```