天天看點

Minimum Depth of Binary Tree Java

/*
    Solution1:
    key to solve: DFS, recursion
    1.Classic DFS recursion
     */
    public int minDepthDFS(TreeNode root) {
        //base case
        if (root == null) return 0;

        //recursion
        int left = minDepthDFS(root.left);
        int right = minDepthDFS(root.right);

        if (left == 0) return left+1;
        if (right == 0) return right+1;

        return Math.min(left, right) + 1;
    }
    /*
    Solution2: BFS ArrayList
    Key to solve: BFS, ArrayList similar with Maximum Depth
    1. the initial depth value start from 1;
    2. Go through Tree by level => BFS
     */
    private int minDepthBFS(TreeNode root){
        if(root==null) return 0;
        List<TreeNode> treeList=new ArrayList<TreeNode>();

        //start from 1
        int depth=1;
        treeList.add(root);

        while(!treeList.isEmpty()){
            List<TreeNode> cur=new ArrayList<TreeNode>();
            for(TreeNode t:treeList) {
                if (t.left == null && t.right == null) return depth;
                if (t.left != null) cur.add(t.left);
                if (t.right != null) cur.add(t.right);
            }
            //clone the current level to TreeList
            treeList=new ArrayList<TreeNode>(cur);
            depth++;
        }
        return depth;
    }