算法面试——二叉树遍历：递归、非递归、重建二叉树

二叉树遍历是算法面试的绝对基础。递归写法要熟练非递归写法要能手撕。一、前序遍历voidpreorder(TreeNoderoot){if(rootnull)return;System.out.print(root.val );preorder(root.left);preorder(root.right);}voidpreorderIter(TreeNoderoot){StackTreeNodestacknewStack();if(root!null)stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();System.out.print(node.val );if(node.right!null)stack.push(node.right);if(node.left!null)stack.push(node.left);}}二、中序遍历voidinorderIter(TreeNoderoot){StackTreeNodestacknewStack();TreeNodecurrroot;while(curr!null||!stack.isEmpty()){while(curr!null){stack.push(curr);currcurr.left;}currstack.pop();System.out.print(curr.val );currcurr.right;}}三、后序遍历最难的非递归ListIntegerpostorderIter(TreeNoderoot){LinkedListIntegerresultnewLinkedList();StackTreeNodestacknewStack();if(root!null)stack.push(root);while(!stack.isEmpty()){TreeNodenodestack.pop();result.addFirst(node.val);// 头插法相当于逆序if(node.left!null)stack.push(node.left);if(node.right!null)stack.push(node.right);}returnresult;// 输出顺序左右根}四、层序遍历ListListIntegerlevelOrder(TreeNoderoot){ListListIntegerresultnewArrayList();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;}五、重建二叉树publicTreeNodebuildTree(int[]preorder,int[]inorder){returnbuild(preorder,0,inorder,0,inorder.length-1);}privateTreeNodebuild(int[]pre,intpreStart,int[]in,intinStart,intinEnd){if(preStartpre.length||inStartinEnd)returnnull;TreeNoderootnewTreeNode(pre[preStart]);introotIdxinStart;while(in[rootIdx]!root.val)rootIdx;intleftLenrootIdx-inStart;root.leftbuild(pre,preStart1,in,inStart,rootIdx-1);root.rightbuild(pre,preStartleftLen1,in,rootIdx1,inEnd);returnroot;} 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。