二叉树的最小深度

• 实现思路
  • 用的是BFS的代码框架
  • 但是需要注意的是结果值的累加控制。只要遇到左右子树都为空的节点就立刻返回当前节点的深度，

  • /**
     * Definition for a binary tree node.
     * public 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;
     *     }
     * }
     */
    class Solution {
        public int minDepth(TreeNode root) {
            return BFS(root);
        }
    
        int BFS(TreeNode root){
            if(root == null) return 0;
            
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
    
            int depth = 1;
            while(!queue.isEmpty()){
                int sz = queue.size();
                for(int i=0; i<sz; i++){
                    TreeNode node = queue.poll();
                    if(node.left != null) queue.offer(node.left);
                    if(node.right != null) queue.offer(node.right);
                    if(node.left==null && node.right==null){
                        return depth;
                    }
                }
                depth++;
            }
            return depth;
        }
    
    }

    
    
    

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int run (TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left != null && root.right != null) {
            return Math.min(run(root.left), run(root.right)) + 1;
        }else if(root.left != null) {
            return run(root.left) + 1;
        }else if(root.right != null) {
            return run(root.right) + 1;
        }else {
            // 该节点为叶子节点
            return 1;
        }
    }
}

    public int run(TreeNode root) {
        if(root==null) return 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int residue=1;//记录该层剩余结点数
        int depth=1;
        while (!queue.isEmpty()){
            int now=0;//记录下一层有多少个结点
            while (residue!=0){
                //遍历该层每个结点,找到叶子结点就退出
                TreeNode curr = queue.poll();
                residue--;
                if (curr.left==null&&curr.right==null){
                    return depth;
                }
                if (curr.left!=null){
                    queue.add(curr.left);
                    now++;
                }
                if (curr.right!=null){
                    queue.add(curr.right);
                    now++;
                }
            }
            depth++;//没有退出,层数加一
            residue=now;//更新该层结点数
        }
        return depth;
    }

public int run(TreeNode root) {
    if(root == null){
        return 0;
    }
    int leftCount = run(root.left);        
    int rightCount =  run(root.right);
    // 判断左右是否存在叶子节点，都存在则取小的，只有一个存在则取大的
    if(root.right!=null&&root.left!=null){
        leftCount = Math.min(leftCount, rightCount);
    }else{
        leftCount = Math.max(leftCount, rightCount);
    }
    return leftCount+1;
}

public int run(Node root) {
        if (root == null) return 0;
        int depth = 1; // the first level is the root
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        nodeQueue.offer(null); // null represent start of new level
        while(!nodeQueue.isEmpty()){
            Node current = nodeQueue.poll();
            if (current != null){
                if (current.left !=null) nodeQueue.offer(current.left);
                if (current.right !=null) nodeQueue.offer(current.right);
                if (current.left == null && current.right == null) return depth;
            }else{
                depth += 1;
                if (!nodeQueue.isEmpty()) nodeQueue.offer(null);
            }

        }
        return depth;
    }

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(null != root.left && null != root.right){
            int leftHeight = minDepth(root.left);
            int rightHeight = minDepth(root.right);
            return Math.min(leftHeight,rightHeight) + 1;
        }
        int leftHeight2 = minDepth(root.left);
        int rightHeight2 = minDepth(root.right);
        //因为找的是叶子节点
        //左右节点只要有一个存在，则路径就需要沿着存在的那个子节点走下去
        //所以直接取最大的那个
        return Math.max(leftHeight2,rightHeight2) + 1;
    }
}

public class Solution {
    private int min(int a,int b){
        return a>b?b:a;
    }
    public int run(TreeNode root) {
        if(root==null)return 0;     //节点为null
        if(root.left==null)return run(root.right)+1;     //左子树为空
        if(root.right==null)return run(root.left)+1;  // 右子树为空
        return min(run(root.left),run(root.right))+1;   //其他

    }
}

	public class Solution {
    public int run(TreeNode root) {



	      // 递归结束条件
        if(root == null){
            return 0;
        }



	      // 获取左子树的深度
        int lDepth = run(root.left);



	      // 获取右子树的深度
        int rDepth = run(root.right);



	



	      // 对没有孩子的结点进行判断
        if(lDepth + rDepth == 0){
            return 1;
        }



	      // 对只有一个孩子的结点进行判断
        if(lDepth * rDepth == 0){
            return lDepth + rDepth + 1;
        }



	      // 对左右子树深度进行最小值求取
        return Math.min(lDepth, rDepth) + 1;
    }
}

//递归
public class Solution {
    public int run(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = run(root.left);
        int right = run(root.right);
        if(left !=0 && right !=0) {
            return (left > right ? right : left) + 1;
        }else{
            return (left > right ? left : right) + 1;
        }
    }
}