算法面试——二叉树：最大深度、验证 BST、层序遍历

二叉树是面试中最高频的数据结构之一。递归写前中后序队列写层序。一、二叉树的最大深度publicintmaxDepth(TreeNoderoot){if(rootnull)return0;returnMath.max(maxDepth(root.left),maxDepth(root.right))1;}二、验证二叉搜索树publicbooleanisValidBST(TreeNoderoot){returnvalidate(root,Long.MIN_VALUE,Long.MAX_VALUE);}privatebooleanvalidate(TreeNodenode,longlow,longhigh){if(nodenull)returntrue;if(node.vallow||node.valhigh)returnfalse;returnvalidate(node.left,low,node.val)validate(node.right,node.val,high);}三、二叉树的层序遍历publicListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresultnewArrayList();if(rootnull)returnresult;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();ListIntegerlevelnewArrayList();for(inti0;isize;i){TreeNodenodequeue.poll();level.add(node.val);if(node.left!null)queue.offer(node.left);if(node.right!null)queue.offer(node.right);}result.add(level);}returnresult;} 觉得有用的话点赞 关注【张老师技术栈】吧