算法-tree-二叉树的最大深度算法

题目地址
我的解法

/** * 2ms 21.07 * 41M 33.17 * 其实是广度优先搜索 * 切入点是一层一层看，根据当前层构建下一层。 * */ public static int maxDepth(TreeNode root) { if (null == root) { return 0; } int deep = 1; List curLevel = new ArrayList<>(); curLevel.add(root); List nextLevel = null; while (hasNextLevel(curLevel)) { nextLevel = new ArrayList<>(); for (TreeNode cur : curLevel) { if (null != cur) { nextLevel.add(cur.left); nextLevel.add(cur.right); } } curLevel = nextLevel; deep ++; } return deep; }

官方-广度优先搜索

/** * 官方的广度优先搜索 * 运用了Queue @see MyQueue * */ public static int maxDepth_l1(TreeNode root) { if (null == root) { return 0; }Queue curLevel = new LinkedList<>(); curLevel.offer(root); int deep = 0; while (!curLevel.isEmpty()) { int size = curLevel.size(); //TODO 固定poll次数 while (size > 0) { TreeNode curNode = curLevel.poll(); if (curNode == null) { continue; } if (curNode.left != null) { curLevel.offer(curNode.left); } if (curNode.right != null) { curLevel.offer(curNode.right); } size --; }//Queue curLevelTemp= curLevel; //for (TreeNode cur : curLevelTemp) {java.util.ConcurrentModificationException //if (cur == null) { //continue; //} //if (cur.left != null) { //curLevel.offer(cur.left); //} //if (cur.right != null) { //curLevel.offer(cur.right); //} //curLevel.poll(); //} deep ++; } return deep; }

官方-深度优先搜索

/** * 官方深度优先搜索 * 运用递归 * 如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 * * max(l,r) + 1 * * 而左子树和右子树的最大深度又可以以同样的方式进行计算。 * */ public static int maxDepth_l2(TreeNode root) { //3 /// \ //920 ///\ //157 if (root == null) { return 0; } else { int maxLeft = maxDepth_l2(root.left); //1 int maxRight = maxDepth_l2(root.right); return Math.max(maxLeft, maxRight) + 1; } }

拓展-DFS&BFS
深度优先搜索算法DFS 【算法-tree-二叉树的最大深度】1、算法步骤：
——访问顶点v；
——依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
——若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止
2、DFS属于盲目搜索。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
广度优先搜索算法BFS 1、算法步骤：
——首先将根节点放入队列中；
——从队列中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中；
——若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”；
——重复步骤2
2、BFS同样属于盲目搜索。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
拓展API-Queue

文章图片

特性 1、线性表/线性队列
2、FIFO
3、表头出，表尾加
implements

Queue queue_ArrayBlockingQueue = new ArrayBlockingQueue<>(10); Queue queue_ArrayDeque = new ArrayDeque<>(); Queue queue_ConcurrentLinkedDeque = new ConcurrentLinkedDeque<>(); Queue queue_LinkedBlockingDeque = new LinkedBlockingDeque<>(); Queue queue_LinkedList = new LinkedList<>();

methods

method	特性
add	队列尾插入，队列满时抛出IllegalStateException
offer	队列尾插入，队列满时返回false
remove	移除并返回头部元素，队列空时，抛出NoSuchElementException
pool	移除并返回头部元素，队列空时，返回null
element	查看队列头元素，队列空时，抛出NoSuchElementException
peek	查看队列头元素，队列空时，返回null

code

public static void main(String[] args) { Queue queue_ArrayBlockingQueue = new ArrayBlockingQueue<>(10); Queue queue_ArrayDeque = new ArrayDeque<>(); Queue queue_ConcurrentLinkedDeque = new ConcurrentLinkedDeque<>(); Queue queue_LinkedBlockingDeque = new LinkedBlockingDeque<>(); Queue queue_LinkedList = new LinkedList<>(); System.out.println("++++++++++++++++++++++++++"); //add 表尾插 ——>[1,2,3] //队列满时，抛出IllegalStateException Queue queue_add = new ArrayBlockingQueue<>(2); queue_add.add(1); queue_add.add(2); try { queue_add.add(3); } catch (Exception e) { System.out.println(e); } for (Integer q : queue_add) { System.out.println(q); }try { Queue queue_LinkedList_add = new LinkedList<>(); for (int i = 0; i < 1000000; i++) { queue_LinkedList_add.add(i); } System.out.println(queue_LinkedList_add.size()); } catch (Exception e) { System.out.println(e); }System.out.println("++++++++++++++++++++++++++"); //offer 表尾插 ——>[1,2,3,4,5,6] //队列满时，返回false Queue queue_offer = new ArrayBlockingQueue<>(4); System.out.println(queue_offer.offer(1)); System.out.println(queue_offer.offer(2)); System.out.println(queue_offer.offer(3)); System.out.println(queue_offer.offer(4)); try { System.out.println(queue_offer.offer(5)); } catch (Exception e) { System.out.println(e); } for (Integer q : queue_offer) { System.out.println(q); }try { Queue queue_LinkedList_offer = new LinkedList<>(); for (int i = 0; i < 1000000; i++) { if (!queue_LinkedList_offer.add(i)) { System.out.println("offer false"); } } System.out.println(queue_LinkedList_offer.size()); } catch (Exception e) { System.out.println(e); } System.out.println("++++++++++++++++++++++++++"); //remove 移除并返回队列头部元素 //队列空时，抛出NoSuchElementException Queue queue_LinkedList_remove = new LinkedList<>(); for (int i = 0; i < 6; i++) { queue_LinkedList_remove.offer(i); } for (int i = 0; i < 7; i++) { try { System.out.println(queue_LinkedList_remove.remove()); } catch (Exception e) { System.out.println(i + " e = " + e); } } System.out.println("++++++++++++++++++++++++++"); //poll 移除并返回队列头部元素 //队列空时，返回null Queue queue_poll = new LinkedList<>(); for (int i = 0; i < 10; i++) { queue_poll.offer(i); } for (int i = 0; i < 11; i++) { try { System.out.println(queue_poll.poll()); } catch (Exception e) { System.out.println(i + " e = " + e); } } System.out.println("++++++++++++++++++++++++++"); //element 返回队列头部元素 //队列空时，抛出NoSuchElementException Queue queue_element = new LinkedList<>(); queue_element.offer(1); queue_element.offer(2); System.out.println(queue_element.element()); System.out.println(queue_element.poll()); System.out.println(queue_element.element()); System.out.println(queue_element.poll()); try { System.out.println(queue_element.element()); } catch (Exception e) { System.out.println(e); } System.out.println("++++++++++++++++++++++++++"); //peek 返回队列头部元素 //队列空时，返回null Queue queue_peek = new LinkedList<>(); for (int i = 0; i < 3; i++) { queue_peek.offer(i); } for (int i = 0; i < 4; i++) { try { System.out.println(queue_peek.peek()); System.out.println(queue_peek.poll()); } catch (Exception e) { System.out.println(i + " e = " + e); } } System.out.println("++++++++++++++++++++++++++"); }