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

二叉树是面试中最高频的数据结构之一。递归写前中后序，队列写层序。

一、二叉树的最大深度

publicintmaxDepth(TreeNoderoot){if(root==null)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(node==null)returntrue;if(node.val<=low||node.val>=high)returnfalse;returnvalidate(node.left,low,node.val)&&validate(node.right,node.val,high);}

三、二叉树的层序遍历

publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();if(root==null)returnresult;Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();List<Integer>level=newArrayList<>();for(inti=0;i<size;i++){TreeNodenode=queue.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;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！