package tree;

/**
 * 111. 二叉树的最小深度
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 *
 * @author Tang
 * @date 2021/7/15
 */
public class MinDepth {

    /**
     * 前序遍历
     * 得左右子节点都是null才行
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        return preSearch(root, 0);
    }

    /**
     * 前序遍历
     * @param height 当前已有高度
     * @param node
     * @return 深度
      */
    private int preSearch(TreeNode node, int height){
        if(node == null){
            return height;
        }
        height += 1;
        if(node.left == null){
            return preSearch(node.right, height);
        }
        if(node.right == null){
            return preSearch(node.left, height);
        }
        int left = preSearch(node.left, height);
        int right = preSearch(node.right, height);
        return Math.min(left, right);
    }


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node1.right = node3;
        node2.right = node5;
        node2.left = node4;
        System.out.println(new MinDepth().minDepth(node1));

    }




}

Leecode no.111 二叉树的最小深度