[leetCode]111.二叉树最小深度

递归

与求二叉树最大深度一样可以使用递归求解，但要注意左子树或右子树为null的情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        else if(root.left == null) return minDepth(root.right)+1;
        else if(root.right == null) return minDepth(root.left)+1;
        else{
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            return Math.min(leftDepth,rightDepth)+1;
        }
    }
}

DFS迭代

使用一个队列，首先加入一个根节点，在迭代中每次从头部取出一个结点，并在尾部加入子节点，当取出结点遇到叶子结点时跟新最小深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair(root, 1));//在链表尾部添加结点
        int min = Integer.MAX_VALUE;
        while(!queue.isEmpty()){
            Pair<TreeNode,Integer> current = queue.poll();//取出链表头部元素
            root = current.getKey();
            int currentDepth = current.getValue();
            if(root.left == null && root.right == null)
                min = Math.min(min, currentDepth);
            if(root.left!=null)
                queue.add(new Pair<TreeNode,Integer>(root.left, currentDepth + 1));
            if(root.right!=null)
                queue.add(new Pair<TreeNode,Integer>(root.right, currentDepth + 1));
        } 
        return min;
    }
}

广度优先搜索

深度优先搜索访问了每个节点，广度优先搜索当遇到叶子节点时退出，使用键值对记录每个节点当前的深度

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair(root, 1));//在链表尾部添加结点
        int currentDepth = 0;
        while(!queue.isEmpty()){
            Pair<TreeNode,Integer> current = queue.poll();//取出链表头部元素
            root = current.getKey();
            currentDepth = current.getValue();
            if(root.left == null && root.right == null)
                break;
            if(root.left!=null)
                queue.add(new Pair<TreeNode,Integer>(root.left, currentDepth + 1));
            if(root.right!=null)
                queue.add(new Pair<TreeNode,Integer>(root.right, currentDepth + 1));
        } 
        return currentDepth;
    }
}

按层遍历

一层一层的遍历，遇到叶子节点则退出,

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);//在链表尾部添加结点
        int current_depth = 0;
        a:while(!queue.isEmpty()){
            int size = queue.size();//当前层的结点数
            current_depth++;
            for(int i = 0; i < size; i++){ 
                root = queue.poll();//取出每一层的每一个结点          
                if(root.left == null && root.right == null){
                    break a;//遇到叶子结点则退出
                }
                if(root.left!=null){
                    queue.add(root.left);
                }
                if(root.right!=null){
                    queue.add(root.right);
                }
            } 
        } 
        return current_depth;
    }
}