public class MinDepth_111 {

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode() {}

TreeNode(int val) {

this.val = val;

}

TreeNode(int val, TreeNode left, TreeNode right) {

this.val = val;

this.left = left;

this.right = right;

}

}

/**

* （错误解法）类似于二叉树的最大深度

* @param root

* @return

*/

public int minDepthError(TreeNode root) {

return root != null ? Math.min(minDepthError(root.left), minDepthError(root.right)) + 1 : 0;

}

/**

* 初看题目很容易写成以上错误写法，题目求的是到叶子节点的最短路径，叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点

* 题目的关键是搞清楚递归执行逻辑：

* 1、当节点左右子节点都为空说明到达了叶子节点直接返回1

* 2、当左右节点有一个不为空，返回不为空节点的递归结果

* 3、当左右节点都不为空，返回左右节点递归结果的最小值

* @param root

* @return

*/

public int minDepth1(TreeNode root) {

if (root == null) return 0;

if (root.left == null && root.right == null) return 1;

if (root.left == null) return minDepth1(root.right) + 1;

if (root.right == null) return minDepth1(root.left) + 1;

return Math.min(minDepth1(root.right), minDepth1(root.left)) + 1;

}

/**

* 针对以上解法可以进行简化：1和2两种情况可以合并为minDepth(root.right)+minDepth(root.left)+1

* @param root

* @return

*/

public int minDepth2(TreeNode root) {

if (root == null) return 0;

return root.left == null || root.right == null ? minDepth2(root.right) + minDepth2(root.left) + 1 :

Math.min(minDepth2(root.right), minDepth2(root.left)) + 1;

}

}