企业官网建设流程全解析

二叉树遍历是算法面试的绝对基础。递归写法要熟练，非递归写法要能手撕。

一、前序遍历

voidpreorder(TreeNoderoot){if(root==null)return;System.out.print(root.val+" ");preorder(root.left);preorder(root.right);}voidpreorderIter(TreeNoderoot){Stack<TreeNode>stack=newStack<>();if(root!=null)stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();System.out.print(node.val+" ");if(node.right!=null)stack.push(node.right);if(node.left!=null)stack.push(node.left);}}

二、中序遍历

voidinorderIter(TreeNoderoot){Stack<TreeNode>stack=newStack<>();TreeNodecurr=root;while(curr!=null||!stack.isEmpty()){while(curr!=null){stack.push(curr);curr=curr.left;}curr=stack.pop();System.out.print(curr.val+" ");curr=curr.right;}}

三、后序遍历（最难的非递归）

List<Integer>postorderIter(TreeNoderoot){LinkedList<Integer>result=newLinkedList<>();Stack<TreeNode>stack=newStack<>();if(root!=null)stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();result.addFirst(node.val);// 头插法，相当于逆序if(node.left!=null)stack.push(node.left);if(node.right!=null)stack.push(node.right);}returnresult;// 输出顺序：左右根}

四、层序遍历

List<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>result=newArrayList<>();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;}

五、重建二叉树

publicTreeNodebuildTree(int[]preorder,int[]inorder){returnbuild(preorder,0,inorder,0,inorder.length-1);}privateTreeNodebuild(int[]pre,intpreStart,int[]in,intinStart,intinEnd){if(preStart>=pre.length||inStart>inEnd)returnnull;TreeNoderoot=newTreeNode(pre[preStart]);introotIdx=inStart;while(in[rootIdx]!=root.val)rootIdx++;intleftLen=rootIdx-inStart;root.left=build(pre,preStart+1,in,inStart,rootIdx-1);root.right=build(pre,preStart+leftLen+1,in,rootIdx+1,inEnd);returnroot;}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！每周更新 Java/Python/爬虫 实战干货，不让你白来。