package week02;

import java.util.LinkedList;

import java.util.Queue;

/**

* @创建人 luoxiang

* @创建时间 2019/6/13 12:27

* @描述 LeetCode : 111. 二叉树的最小深度 https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

* 五毒神掌 ： 隔一周练习一次

*/

public class MinimunDepthBinaryTree111 {

public static void main(String[] args) {

TreeNode node = new TreeNode(5);

node.left = new TreeNode(1);

node.right = new TreeNode(4);

node.left.left = new TreeNode(3);

node.left.right = new TreeNode(6);

System.out.println(new MinimunDepthBinaryTree111().minDepth3(node));

}

/**

* Method 1 : DFS 递归解决

* 时间复杂度 : O(N) ;

* 空间复杂度 ： O(N) ;

*/

public int minDepth(TreeNode root) {

if (root == null) return 0;

int left = minDepth(root.left);

int right = minDepth(root.right);

return (left == 0 || right == 0) ? right + left + 1 : Math.min(left, right) + 1;

}

/**

* Method 2 : 方法一 DFS 精简版

* 时间复杂度 ： O(N) ;

* 空间复杂度 ： O(1); 没有额外的空间开销

*/

public int minDepth2(TreeNode root) {

if (root == null) return 0;

return (root.left == null || root.right == null) ? minDepth(root.right) + minDepth(root.left) + 1 : Math.min(minDepth(root.left), minDepth(root.right)) + 1;

}

/**

* Method 3 : BFS 迭代 ； 使用队列 ; depth 记录深度；currentSize 记录当前层的数量； 只有数量为0时，当前层才算是深度加1；

* 时间复杂度 : O(N) ;

* * 空间复杂度 : O(N) ;

*/

public int minDepth3(TreeNode root) {

if (root == null) return 0;

Queue<TreeNode> queue = new LinkedList<>();

queue.offer(root);

int depth = 1,currentSize = 1;

while (!queue.isEmpty()) {

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;

if (--currentSize == 0) {

depth++;

currentSize = queue.size();

}

}

return depth;

}

}